Al Zimmermann - Sums and Products

[dmd]

Pavlovsky в сообщении #1078591 писал(а):

Может кто подскажет. Что это такое и как его вычислить?
g a primitive root of F(p).

F(p) конечное поле, p простое число.

В pari/gp есть функция znprimroot, в Вольфраматике и в WolframAlpha - PrimitiveRoot.

[Pavlovsky]

Спасибо, я уже нашел по ссылке данной WhiteFox.

Первые 10000 тривиальных корней.
https://oeis.org/A046145/b046145.txt

[Pavlovsky]

Продолжаю изучать статью A REVIEW OF THE AVAILABLE CONSTRUCTION METHODS FOR GOLOMB RULERS

Может кто подскажет?

Теорема 4. Последовательность строится с помощью: g a primitive root in $F(q^2)$. После теоремы рассматривается пример №3. Там получается поле $F(16)$, но у него нет примитивных корней. Как же они тогда строят решение?

[whitefox]

В том примере прямо указан примитивный элемент этого поля — многочлен $x$ и указаны все ненулевые элементы поля $\mathbb{F}_{16}$ — различные степени многочлена $x,$ приведённые по модулю $x^4+x+1$ с приведением коэффициентов по модулю 2.

-- 02 дек 2015, 15:55 --

Подробности построения конечных полей.

[Pavlovsky]

Несколько раз читал про конечные поля, непонятки увы остались. Может подскажешь, по быстрому. Нам ведь нужны числа, а не многочлены. Как задается соответствие между ними.

[whitefox]

Если порядок поля $\mathbb{F}_q$ простое число $q=p,$ то элементами поля являются вычеты по модулю $p.$ Но если порядок поля — не единичная степень простого $q=p^n\ (n>1),$ то всё не так просто. В этом случае ненулевые элементы поля представляются многочленами степени не больше $n-1$ над полем $\mathbb{F}_p$ (то есть коэффициенты этих многочленов — суть вычеты по модулю $p$). Соответствия между элементами такого поля и числами нет. Но можно представлять элементы $n$-мерными векторами над полем $\mathbb{F}_p$ (пример такого представления для поля $\mathbb{F}_{16}$ дан в википедии по указанной ссылке).

Но нам числа и не нужны, ведь при построении множества $S$ проверяется условие $g^i-g\in\mathbb{F}_q,$ где $g$ — примитивный элемент нашего поля $\mathbb{F}_{q^2}.$ То есть для Примера 3 нужно проверять чтобы многочлен $x^i-x$ принадлежал полю $\mathbb{F}_4$ (точнее, подполю поля $\mathbb{F}_{16},$ изоморфному полю $\mathbb{F}_4$).

[jcmeyrignac]

Large Golomb rulers, with Sidon sets:
http://www.cs.utoronto.ca/~apostol/golomb/

[Pavlovsky]

Потихоньку наступает просветление.
Есть ли смысл программировать алгоритм Bose-Chowla (Теорема 4)? Или это слишком сложно? Вроде как упрощает задачу, что все задания в конкуре - простые числа. Построить $\mathbb{F}_{p^2}.$ и выполнить предписанные алгоритмом манипуляции вроде несложно?!

-- Ср дек 02, 2015 21:31:59 --

Афигеть.

[whitefox]

Pavlovsky в сообщении #1078861 писал(а):

Есть ли смысл программировать алгоритм Bose-Chowla (Теорема 4)?

http://www.cs.toronto.edu/~apostol/golomb/main.pdf
В приложении к этой статье есть C++ код алгоритма Bose-Chowla.

[Pavlovsky]

Все уже посчитано до нас до 65000.

-- Ср дек 02, 2015 22:51:12 --

Apostolos Dimitromanolakis - гений.

[whitefox]

Действительно, "всё уже украдено до нас".
Я ссылку jcmeyrignac только мельком глянул, не вникая.

[dimkadimon]

Уже 2х30.0. Неужели и это соревнование тоже закончилось?

[Pavlovsky]

Лидеры еще что то знают, чего мы не знаем. Результаты Apostolos Dimitromanolakis заметно хуже оптимальных для маленьких N.

[Pavlovsky]

dimkadimon в сообщении #1078939 писал(а):

Неужели и это соревнование тоже закончилось?

Не может такого быть, чтобы были найдены оптимумы. Скорее всего это предел некоего стандартного подхода.

[dimkadimon]

Pavlovsky в сообщении #1079028 писал(а):

Не может такого быть, чтобы были найдены оптимумы. Скорее всего это предел некоего стандартного подхода.

Хм подозреваю что улучшений уже не будет и это соревнование практически закончено тоже. Лучшие результаты нашел используя программу conpp, может кому поможет:
http://www.research.ibm.com/people/s/sh ... rprog.html