Редкий правитель

— Разреженная линейка это линейка, в которой могут отсутствовать некоторые метки расстояний. Говоря более абстрактно, разреженная линейка длины $L$ с $m$ отметки — это последовательность целых чисел $a_{1},a_{2},...,a_{m}$ где $0=a_{1}<a_{2}<...<a_{m}=L$ . Знаки $a_{1}$ и $a_{m}$ соответствуют концам линейки. Чтобы измерить расстояние $K$ , с $0\leq K\leq L$ должны быть отметки $a_{i}$ и $a_{j}$ такой, что $a_{j}-a_{i}=K$ .

Полная разреженная линейка позволяет измерить любое целое расстояние вплоть до его полной длины. Полная разреженная линейка называется минимальной , если не существует полной разреженной линейки длины $L$ с $m-1$ отметки. Другими словами, если удалить любую из меток, вы больше не сможете измерить все расстояния, даже если метки можно было бы переставить. Полная разреженная линейка называется максимальной , если не существует полной разреженной линейки большей длины с $m$ отметки. Полные минимальные линейки длиной 135 и 136 требуют на одну метку больше, чем линейки длиной 124–134, 137 и 138. Разреженная линейка называется оптимальной, если она одновременно минимальна и максимальна.

Так как число различных пар меток равно $m(m-1)/2$ , это верхняя граница длины $L$ любой максимальной разреженной линейки с $m$ отметки. Эта верхняя граница может быть достигнута только за 2, 3 или 4 балла. При большем количестве отметок разница между оптимальной длиной и границей растет постепенно и неравномерно.

Например, для 6 отметок верхняя граница равна 15, но максимальная длина равна 13. Существует 3 различные конфигурации разреженных линеек длиной 13 с 6 отметками. Один – {0, 1, 2, 6, 10, 13}. Чтобы измерить длину, скажем, 7, с помощью этой линейки нужно взять расстояние между отметками 6 и 13.

Линейка Голомба — это редкая линейка, требующая всех различий. $a_{j}-a_{i}$ быть отчетливым. В общем, голомбский правитель с $m$ отметки будут значительно длиннее, чем оптимальная разреженная линейка с $m$ отметки, поскольку $m(m-1)/2$ — нижняя граница длины линейки Голомба. В длинной линейке Голомба будут пробелы, то есть расстояния, которые она не сможет измерить. Например, оптимальная линейка Голомба {0, 1, 4, 10, 12, 17} имеет длину 17, но не может измерять длины 14 или 15.

Правители Вихмана

Многие оптимальные линейки имеют вид $W(r,s)=1^{r},r+1,(2r+1)^{r},(4r+3)^{s},(2r+2)^{(r+1)},1^{r},$ где $a^{b}$ представляет $b$ сегменты длины $a$ . Таким образом, если $r=1$ и $s=2$ , затем $W(1,2)$ имеет (по порядку):
1 отрезок длиной 1,
1 отрезок длиной 2,
1 отрезок длиной 3,
2 отрезка длиной 7,
2 сегмента длиной 4,
1 отрезок длиной 1.

Младший вариант - $w(r,s)=1^{r},r+1,(2r+1)^{(r+1)},(4r+3)^{s},(2r+2)^{r},1^{r},$ , длиной на единицу меньше $W(r,s)$ .

$W(1,2)$ дает линейку {0, 1, 3, 6, 13, 20, 24, 28, 29}, а $w(1,2)$ дает {0, 1, 3, 6, 9, 16, 23, 27, 28}. Длина линейки Вихмана равна $4r(r+s+2)+3(s+1)$ и количество отметок $4r+s+3$ . Обратите внимание, что не все линейки Вихмана оптимальны, и не все оптимальные линейки могут быть созданы таким образом. Ни одна из оптимальных линеек длиной 1, 13, 17, 23 и 58 не следует этому шаблону. Эта последовательность заканчивается числом 58, если гипотеза Питера Лушни об оптимальной линейке верна. Известно, что гипотеза верна для длины 213. ^[1]

Асимптотика

Для каждого $n$ позволять $l(n)$ — наименьшее количество отметок на линейке длины $n$ . Например, $l(6)=4$ . Асимптотика функции $l(n)$ изучал Эрдос, Гал ^[2] (1948) и продолжение Лича ^[3] (1956) которые доказали, что предел $\lim _{n\to \infty }{l(n)^{2}}/n$ существует и ограничен снизу и сверху
$2+{\tfrac {4}{3\pi }}=2.424...<2.434...=\max _{0<\theta <2\pi }2(1-{\tfrac {\sin(\theta )}{\theta }})\leq \lim _{n\to \infty }{\frac {l(n)^{2}}{n}}\leq {\frac {375}{112}}=3.348...$

Гораздо лучшие верхние оценки существуют для $n$ - идеальные правители. Это подмножества $A$ из $\mathbb {N}$ такое, что каждое положительное число $k\leq n$ можно записать как разницу $k=a-b$ для некоторых $a,b\in A$ . Для каждого номера $n$ позволять $k(n)$ быть наименьшей мощностью $n$ - идеальный правитель. Ясно, что $k(n)\leq l(n)$ . Асимптотика последовательности $k(n)$ изучался Редеем, Реньи ^[4] (1949), а затем Лича (1956) и Голея. ^[5] (1972). Их усилиями были получены следующие верхние и нижние оценки:
$\max _{0<\theta <2\pi }2(1-{\tfrac {\sin(\theta )}{\theta }})\leq \lim _{n\to \infty }{\frac {k(n)^{2}}{n}}=\inf _{n\in \mathbb {N} }{\frac {k(n)^{2}}{n}}\leq {\frac {128^{2}}{6166}}=2.6571...<{\frac {8}{3}}.$

Определим избыток как $E(n)=l(n)-\lceil {\sqrt {3n+{\tfrac {9}{4}}}}\rfloor$ . В 2020 году Пегг экспериментально доказал, что $E(n)$ ≤ 1 для всех длин $n$ . ^[6] Если гипотеза об оптимальной линейке верна, то $E(n)=0|1$ для всех $n$ , что приводит к рисунку «темных мельниц» при расположении в столбцах, OEIS A326499. ^[7] Все окна в узоре темных мельниц представляют собой линейки Вихмана. Ни один из самых известных редких правителей $n>213$ по состоянию на сентябрь 2020 года минимальны. Многие из наиболее известных на данный момент $E=1$ конструкции для $n>213$ считаются неминимальными, особенно «облачные» значения.

Рис 1. Светлые цифры +0, темные цифры +1 для минимального превышения отметки по разреженной линейке. Все минимальные значения до длины 213 доказаны.
Рис 2. «Темные мельницы в пасмурный день» — NJA Sloane. Превышение шаблона для разреженных линеек, наиболее известные значения для L>213.

Примеры

Ниже приведены примеры минимальных разреженных линеек. Выделены оптимальные линейки. Когда их слишком много, чтобы перечислить, включены не все. Зеркальные изображения не отображаются.

Длина	Знаки	Число	Примеры	Форма списка	Вихманн
1	2	1	II	{0, 1}
2	3	1	III	{0, 1, 2}
3	3	1	II.I	{0, 1, 3}	Вт(0,0)
4	4	2	III.I II.II	{0, 1, 2, 4} {0, 1, 3, 4}
5	4	2	III..я II.II	{0, 1, 2, 5} {0, 1, 3, 5}
6	4	1	II..II	{0, 1, 4, 6}	Вт(0,1)
7	5	6	ИИИ...я III.I..I III..II II.III II.I..II II..II.I	{0, 1, 2, 3, 7} {0, 1, 2, 4, 7} {0, 1, 2, 5, 7} {0, 1, 3, 5, 7} {0, 1, 3, 6, 7} {0, 1, 4, 5, 7}
8	5	4	III..I..I II.I...II II..III II...II.I	{0, 1, 2, 5, 8} {0, 1, 3, 7, 8} {0, 1, 4, 6, 8} {0, 1, 5, 6, 8}
9	5	2	III...я...я II..I..II	{0, 1, 2, 6, 9} {0, 1, 4, 7, 9}	- Вт(0,2)
10	6	19	ИИИ..Я...я	{0, 1, 2, 3, 6, 10}
11	6	15	ИИИ...я...я	{0, 1, 2, 3, 7, 11}
12	6	7	ИИИ....Я...я III...I..I..I II.II....II II.I...I...II II..II....II II..I..I..II II.....II.II	{0, 1, 2, 3, 8, 12} {0, 1, 2, 6, 9, 12} {0, 1, 3, 5, 11, 12} {0, 1, 3, 7, 11, 12} {0, 1, 4, 5, 10, 12} {0, 1, 4, 7, 10, 12} {0, 1, 7, 8, 10, 12}	- - - - - Вт(0,3) -
13	6	3	III...я...я..я II..II.....II II....I..III	{0, 1, 2, 6, 10, 13} {0, 1, 4, 5, 11, 13} {0, 1, 6, 9, 11, 13}
14	7	65	ИИИИИ....Я....Я	{0, 1, 2, 3, 4, 9, 14}
15	7	40	II.I..I...I...II II..I..I..I..II	{0, 1, 3, 6, 10, 14, 15} {0, 1, 4, 7, 10, 13, 15}	Вт(1,0) Вт(0,4)
16	7	16	ИИИ....Я...Я...я	{0, 1, 2, 3, 8, 12, 16}
17	7	6	ИИИ....Я....Я...я III...я...я...я..я III.....I...II.I III.....I...I..II II..I.....II.II II......I..III	{0, 1, 2, 3, 8, 13, 17} {0, 1, 2, 6, 10, 14, 17} {0, 1, 2, 8, 12, 14, 17} {0, 1, 2, 8, 12, 15, 17} {0, 1, 4, 10, 12, 15, 17} {0, 1, 8, 11, 13, 15, 17}
18	8	250	II..I..I..I..I..II	{0, 1, 4, 7, 10, 13, 16, 18}	Вт(0,5)
19	8	163	ИИИИИ....Я....Я....Я	{0, 1, 2, 3, 4, 9, 14, 19}
20	8	75	ИИИИИ.....Я....Я....Я	{0, 1, 2, 3, 4, 10, 15, 20}
21	8	33	ИИИИИ.....Я.....Я....Я	{0, 1, 2, 3, 4, 10, 16, 21}
22	8	9	ИИИ....Я....Я....Я...я III.......I....I..I..II II.II.......II.....II II.I..I......I...I...II II.I.....I.....I...II.I II..II....II....II II....II..I.......III II....I..I......III II.....II........II.II	{0, 1, 2, 3, 8, 13, 18, 22} {0, 1, 2, 10, 15, 18, 21, 22} {0, 1, 3, 5, 14, 15, 21, 22} {0, 1, 3, 6, 13, 17, 21, 22} {0, 1, 3, 9, 15, 19, 20, 22} {0, 1, 4, 5, 12, 14, 20, 22} {0, 1, 6, 7, 10, 18, 20, 22} {0, 1, 6, 9, 16, 18, 20, 22} {0, 1, 7, 8, 17, 18, 20, 22}	- - - Вт(1,1) - - - - -
23	8	2	III........I...I..I..II II..I.....I.....II.II	{0, 1, 2, 11, 15, 18, 21, 23} {0, 1, 4, 10, 16, 18, 21, 23}
24	9	472	ИИИИИ......Я.....Я.....Я	{0, 1, 2, 3, 4, 5, 12, 18, 24}
25	9	230	ИИИИИ......Я......Я.....Я	{0, 1, 2, 3, 4, 5, 12, 19, 25}
26	9	83	ИИИИИ.....Я....Я.....Я....Я	{0, 1, 2, 3, 4, 10, 15, 21, 26}
27	9	28	ИИИИИ.....Я.....Я.....Я....Я	{0, 1, 2, 3, 4, 10, 16, 22, 27}
28	9	6	III..........I....I..I..I..II II.III.........II.......II II.I..I..I......I......I...II II.I.....I.....I.....I...II.I II.....I...I.......I..I.II.I II......II......II.III	{0, 1, 2, 13, 18, 21, 24, 27, 28} {0, 1, 3, 5, 7, 18, 19, 27, 28} {0, 1, 3, 6, 9, 16, 23, 27, 28} {0, 1, 3, 9, 15, 21, 25, 26, 28} {0, 1, 7, 11, 20, 23, 25, 26, 28} {0, 1, 9, 10, 21, 22, 24, 26, 28}
29	9	3	III...........I...I..I..I..II II.I..I......I......I...I...II II..I.....I.....I.....II.II	{0, 1, 2, 14, 18, 21, 24, 27, 29} {0, 1, 3, 6, 13, 20, 24, 28, 29} {0, 1, 4, 10, 16, 22, 24, 27, 29}	- Вт(1,2) -
35	10	5	III..............I...I..I..I..I..II II.I..I..I......I......I......I...II II.I..I..I.......I...I......I...II II..II..........II.....II....II II..I.....I.....I.....I.....II.II	{0, 1, 2, 17, 21, 24, 27, 30, 33, 35} {0, 1, 3, 6, 9, 16, 23, 30, 34, 35} {0, 1, 3, 6, 9, 19, 23, 30, 34, 35} {0, 1, 4, 5, 16, 18, 25, 27, 33, 35} {0, 1, 4, 10, 16, 22, 28, 30, 33, 35}
36	10	1	II.I..I......I......I......I...I...II	{0, 1, 3, 6, 13, 20, 27, 31, 35, 36}	Вт(1,3)
43	11	1	II.I..I......I......I......I......I...I...II	{0, 1, 3, 6, 13, 20, 27, 34, 38, 42, 43}	Вт(1,4)
46	12	342	III..I....I....I..........I.....I.....I.....III	{0, 1, 2, 5, 10, 15, 26, 32, 38, 44, 45, 46}	Вт(2,1)
50	12	2	IIII...................Я....Я...Я...Я...Я...И..И..Я II.I..I......I......I......I......I......I...I...II	{0, 1, 2, 3, 23, 28, 32, 36, 40, 44, 47, 50} {0, 1, 3, 6, 13, 20, 27, 34, 41, 45, 49, 50}	- Вт(1,5)
57	13	12	III..Я....Я....Я..........Я..........Я.....Я.....Я.. ...III II.I..I......I......I......I......I......I......I.. .I...II	{0, 1, 2, 5, 10, 15, 26, 37, 43, 49, 55, 56, 57} {0, 1, 3, 6, 13, 20, 27, 34, 41, 48, 52, 56, 57}	Вт(2,2) Вт(1,6)
58	13	6	IIII........................Я....Я...Я...Я...Я...Я...Я ..я..я III...II.......I........I........I........I..I......I ..II III.....I......II.........Я.........Я......Я..Я... II.I II.И..И..........И..И......Я......Я.......И...Я .. Я...II II.I..I..........I......I..I..........I......I...I. ..Я...II II...I..I...I........I.......I........I........I.. ..II.II	{0, 1, 2, 3, 27, 32, 36, 40, 44, 48, 52, 55, 58} {0, 1, 2, 6, 8, 17, 26, 35, 44, 47, 54, 57, 58} {0, 1, 2, 8, 15, 16, 26, 36, 46, 49, 53, 55, 58} {0, 1, 3, 6, 17, 20, 27, 35, 45, 49, 53, 57, 58} {0, 1, 3, 6, 17, 24, 27, 38, 45, 49, 53, 57, 58} {0, 1, 5, 8, 12, 21, 30, 39, 48, 53, 54, 56, 58}
68	14	2	III..Я....Я....Я..........Я..........Я..........Я... ..Я.....Я.....III III.....I......II.........Я.........Я.........Я...... ...И..Я...II.И	{0, 1, 2, 5, 10, 15, 26, 37, 48, 54, 60, 66, 67, 68} {0, 1, 2, 8, 15, 16, 26, 36, 46, 56, 59, 63, 65, 68}	Вт(2,3) -
79	15	1	III..Я....Я....Я..........Я..........Я..........Я... ......Я.....Я.....Я.....III	{0, 1, 2, 5, 10, 15, 26, 37, 48, 59, 65, 71, 77, 78, 79}	Вт(2,4)
90	16	1	III..Я....Я....Я..........Я..........Я..........Я... .......Я..........Я.....Я.....Я.....III	{0, 1, 2, 5, 10, 15, 26, 37, 48, 59, 70, 76, 82, 88, 89, 90}	Вт(2,5)
101	17	1	III..Я....Я....Я..........Я..........Я..........Я... .......Я..........Я..........Я.....Я.....Я.....III	{0,1,2,5,10,15,26,37,48,59,70,81,87,93,99,100,101}	Вт(2,6)
112	18	1	III..Я....Я....Я..........Я..........Я..........Я... .......Я..........Я..........Я..........Я.....Я... ..Я.....III	{0,1,2,5,10,15,26,37,48,59,70,81,92,98,104,110,111,112}	Вт(2,7)
123	19	2	IIII...I......I......I......I..............I....... .....Я..............Я..............Я.......Я...... .I.......I.......III III..Я....Я....Я..........Я..........Я..........Я... .......Я..........Я..........Я..........Я....... .Я.....Я.....Я.....III	{0,1,2,3,7,14,21,28,43,58,73,88,96,104,112,120,121,122,123} {0,1,2,5,10,15,26,37,48,59,70,81,92,103,109,115,121,122,123}	Вт(3,4) Вт(2,8)
138	20	1	IIII...I......I......I......I..............I....... .....Я..............Я..............Я.............. Я.......Я.......Я.......Я.......IIII	{0,1,2,3,7,14,21,28,43,58,73,88,103,111,119,127,135,136,137,138}	Вт(3,5)

Неполные разреженные линейки

Несколько неполных линеек могут полностью измерить расстояние на большее расстояние, чем оптимальная разреженная линейка с таким же количеством отметок. $\{0,2,7,14,15,18,24\}$ , $\{0,2,7,13,16,17,25\}$ , $\{0,5,7,13,16,17,31\}$ , и $\{0,6,10,15,17,18,31\}$ каждая может измерять до 18, тогда как оптимальная разреженная линейка с 7 отметками может измерять только до 17. В таблице ниже перечислены эти линейки вплоть до линеек с 13 отметками. Зеркальные изображения не отображаются. Линейки, которые могут полностью измерить расстояние на большее расстояние, чем любая более короткая линейка с таким же количеством отметок, подсвечиваются.

Знаки	Длина	Размеры до	Правитель
7	24	18	{0, 2, 7, 14, 15, 18, 24}
7	25	18	{0, 2, 7, 13, 16, 17, 25}
7	31	18	{0, 5, 7, 13, 16, 17, 31}
7	31	18	{0, 6, 10, 15, 17, 18, 31}
8	39	24	{0, 8, 15, 17, 20, 21, 31, 39}
10	64	37	{0, 7, 22, 27, 28, 31, 39, 41, 57, 64}
10	73	37	{0, 16, 17, 28, 36, 42, 46, 49, 51, 73}
11	68	44	{0, 7, 10, 27, 29, 38, 42, 43, 44, 50, 68}
11	91	45	{0, 18, 19, 22, 31, 42, 48, 56, 58, 63, 91}
12	53	51	{0, 2, 3, 6, 9, 17, 25, 33, 41, 46, 51, 53}
12	60	51	{0, 5, 9, 13, 19, 26, 33, 48, 49, 50, 51, 60}
12	73	51	{0, 2, 3, 10, 17, 23, 35, 42, 46, 47, 51, 73}
12	75	51	{0, 2, 10, 13, 29, 33, 36, 45, 50, 51, 57, 75}
12	82	51	{0, 8, 28, 31, 34, 38, 45, 47, 49, 50, 74, 82}
12	83	51	{0, 2, 10, 24, 25, 29, 36, 42, 45, 73, 75, 83}
12	85	51	{0, 8, 10, 19, 35, 41, 42, 47, 55, 56, 59, 85}
12	87	51	{0, 12, 24, 26, 37, 39, 42, 43, 46, 47, 75, 87}
13	61	59	{0, 2, 3, 6, 9, 17, 25, 33, 41, 49, 54, 59, 61}
13	69	59	{0, 6, 10, 15, 22, 30, 38, 55, 56, 57, 58, 59, 69}
13	69	59	{0, 6, 11, 15, 22, 30, 38, 55, 56, 57, 58, 59, 69}
13	82	59	{0, 4, 5, 9, 25, 27, 39, 42, 50, 53, 56, 63, 82}
13	83	59	{0, 1, 2, 24, 34, 36, 38, 43, 51, 54, 57, 82, 83}
13	88	59	{0, 1, 3, 9, 16, 26, 36, 40, 47, 54, 58, 59, 88}
13	88	59	{0, 1, 5, 29, 34, 36, 47, 48, 50, 56, 58, 73, 88}
13	90	59	{0, 7, 12, 16, 37, 38, 43, 55, 56, 57, 58, 66, 90}
13	91	59	{0, 5, 9, 12, 16, 32, 38, 42, 55, 56, 57, 63, 91}
13	92	59	{0, 6, 10, 13, 25, 34, 39, 54, 55, 56, 57, 65, 92}
13	94	59	{0, 1, 3, 16, 28, 37, 45, 48, 54, 55, 59, 78, 94}
13	95	59	{0, 4, 32, 37, 38, 40, 48, 53, 54, 56, 63, 83, 95}
13	96	59	{0, 3, 7, 27, 37, 39, 50, 55, 56, 58, 72, 81, 96}
13	101	59	{0, 4, 24, 37, 43, 45, 52, 54, 55, 59, 77, 81, 101}
13	108	59	{0, 8, 17, 40, 50, 53, 64, 65, 69, 71, 91, 99, 108}
13	113	61	{0, 6, 22, 36, 45, 47, 57, 60, 64, 65, 91, 97, 113}
13	133	60	{0, 26, 29, 40, 42, 46, 67, 74, 79, 89, 97, 98, 133}

См. также

Ссылки

^ Робисон, А.Д. Параллельное вычисление разреженных линеек. Зона разработчиков Intel. https://web.archive.org/web/20210330141047/https://software.intel.com/content/www/us/en/develop/articles/parallel-computation-of-sparse-rulers.html
^ Эрдеш, П.; Галь И.С. О представительстве $1,2,\cdots ,N$ по различиям. Недерл. Акад. Wetensch., Proc. 51 (1948) 1155--1158 = Indagationes Math. 10 , 379--382 (1949)
^ Пиявка, Джон. О представительстве $1,2,\cdots ,n$ по различиям. Дж. Лондон Математика. Соц. 31 (1956), 160--169
^ Редей, Л.; Реньи А. О представлении чисел $1,2,\cdots ,N$ посредством различий. (русский) Мат. Сборник НС 24(66), (1949). 385--389.
^ Голей, Марсель Дж.Э. Заметки об изображении $1,\,2,\,\ldots ,\,n$ по различиям. Дж. Лондон Математика. Соц. (2) 4 (1972), 729-734.
^ Пегг, Э. Достижение всех целей: исследование новых границ для редких линеек и доказательство на языке Wolfram. https://blog.wolfram.com/2020/02/12/hitting-all-the-marks-exploring-new-bounds-for-sparse-rulers-and-a-wolfram-language-proof/
^ Слоан, Нью-Джерси (ред.). «Последовательность A326499» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.

[1] Робисон, А.Д. Параллельное вычисление разреженных линеек. Зона разработчиков Intel. https://web.archive.org/web/20210330141047/https://software.intel.com/content/www/us/en/develop/articles/parallel-computation-of-sparse-rulers.html

[2] Эрдеш, П.; Галь И.С. О представительстве $1,2,\cdots ,N$ по различиям. Недерл. Акад. Wetensch., Proc. 51 (1948) 1155--1158 = Indagationes Math. 10 , 379--382 (1949)

[3] Пиявка, Джон. О представительстве $1,2,\cdots ,n$ по различиям. Дж. Лондон Математика. Соц. 31 (1956), 160--169

[4] Редей, Л.; Реньи А. О представлении чисел $1,2,\cdots ,N$ посредством различий. (русский) Мат. Сборник НС 24(66), (1949). 385--389.

[5] Голей, Марсель Дж.Э. Заметки об изображении $1,\,2,\,\ldots ,\,n$ по различиям. Дж. Лондон Математика. Соц. (2) 4 (1972), 729-734.

[6] Пегг, Э. Достижение всех целей: исследование новых границ для редких линеек и доказательство на языке Wolfram. https://blog.wolfram.com/2020/02/12/hitting-all-the-marks-exploring-new-bounds-for-sparse-rulers-and-a-wolfram-language-proof/

[oeis-7] Слоан, Нью-Джерси (ред.). «Последовательность A326499» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.

[1]

[2]

[3]

[4]

[5]

[6]

[7]