Улучшено (?) решение Эрдёша по остроугольным треугольникам

[grizzly]

yk2ru
Это Вы комментируете попытку Sender? Да он попытался именно так, при этом обостряются все прямые углы на гранях, но все диагональные прямые (24 угла) остаются прямыми. Он же сам и заметил это.

[yk2ru]

grizzly в сообщении #1225801 писал(а):

диагональные прямые (24 угла) остаются прямыми.

А если брать не куб, а близко к кубу фигуру, чтобы каждая грань была похожа на трапецию, несильно отличающуюся от квадрата. Будут два острых угла, и два тупых, близких к 90 градусам. А по четвёртому измерению двигать те точки, к которым примыкают тупые, но почти прямые углы, с целью их уменьшения. Может получится?

[grizzly]

yk2ru в сообщении #1226138 писал(а):

Может получится?

Я думаю, что нет. Но было бы здорово, если бы Вы попробовали -- а вдруг? (Если бы я думал, что получится, я бы и сам не поленился попробовать :)

[grizzly]

Бывает понимание типа просветления, а бывает и так, что варится какой-то вопрос в голове на медленном огне и со временем оно само приходит -- понимание. Дофаминовая награда за последнее обычно небольшая (чаще наоборот, испытываешь разочарование -- почему, мол, раньше не догадался), но в сухом остатке одно и то же.

Я посмотрел вот на это:

grizzly в сообщении #1225523 писал(а):

Вершина -- точка "сверху" по центру, как обычно (про неё можно забыть -- она имеет большой запас прочности).

и подумал, а что будет, если поэксплуатировать имеющийся запас прочности. Выбросить девятую точку и построить из восьми точек такое остроугольное множество в $R^4$, у которого минимизирован наибольший угол.

Получился неожиданно красивый симметричный многогранник (использован только один параметр $792=1000-208; 104=208/2$; я теперь работаю в целочисленной решётке):

    a1     a2   a3    a4    a5    a6     a7    a8
x  208  792     0    1000   0     1000   208  792
y  208    0   792    1000   0     208   1000  792
z  208    0     0    208    792   1000  1000  792
t  792    0   104    208    208   104     0   792

Собственно, теперь мне понятно, как были взаимосвязаны числа по четвёртой координате в моём примере на 9 точек (на непонимание этого момента я несколько раз жаловался раньше).

А с $R^5$ всё настолько сложнее, что у меня время от времени возникают сомнения в "формуле grizzly" Но я ещё попытаюсь.

[grizzly]

heptagon в сообщении #1223983 писал(а):

Удалось ли Вам достичь какого-либо прогресса (относительно 12 точек) в размерности 5?

Теперь да. На сегодня имеем новый мировой рекорд из 16 точек.

a=( 120,         120,         120,         120,         750    );
b=( 999,           1,           1,           1,           0    );
c=( 0.0001,    999.9999,      0.0001,      0.0001,      63.443   );
d=( 999.99999, 999.99999,        0,           0,        64.073   );
e=( 0,            0,        999.999989,     0.000009,   64.074   );
f=( 999.99999,    0,        999.999999,     0.000009,   64.076   );
g=( 0.000008,   999.99999,   999.999988,    0.000009,   64.218   );
h=( 999.999989,   1000,        1000,        0.000009,   64.075   );
                                                                                
k=( 0.000011,   0,         0,         999.999991,   64.075   );
l=( 999.999992, 0.00001,  0.000012,   999.999991,   64.218   );
m=( 0.00001,   1000,      0.000001,   999.999991,   64.076   );
n=( 1000,      1000,      0.000011,   999.999991,   64.074   );
o=( 0.00001,   0.00001,    1000,      1000,         64.073   );
p=( 999.9999,  0.0001,    999.9999,   999.9999,     63.443   );
q=( 1,         999,        999,       999,          0        );
r=( 880,       880,        880,       880,          750      );

Каждая точка по первым 4-м координатам достаточно близко "привязана" к вершинам 4D куба, одна из главных диагоналей которого проходит через точки (0,0,0,0) и (1000, 1000, 1000, 1000). Собственно, это и даёт 16 точек.

grizzly в сообщении #1224015 писал(а):

И да, я не пытался побить рекорд в 12 точек -- я пока надеюсь найти все 17.

Ну что же, нацеленность на максимальный результат, не размениваясь по мелким рекордам, себя оправдала (это только у легко- и тяжело- атлетов есть смысл рекорды бить по 1 копейке :)

В этом раскладе не хватает ещё одной точки -- 17-й. Увы, с этим вышла заминка. С самого начала я начал формировать основу "пирамидки" и использовал весь запас прочности (см. мои предыдущие сообщения с туманными пояснениями). Теперь вершинка пирамидки совсем чуть-чуть, но не вписывается. И это не лечится мелкими подвижками -- нужно начинать строить всю конструкцию сначала. (А всего-то нужно было взять в самой первой строчке числа поменьше -- именно с этой точки я начинаю построение.)

Теперь мне переделывать ради 17-й точки уже не хватает внутренней мотивации, поскольку ответ для меня очевиден, и в общей формуле $|S|=2^{d-1}+1$ сомнений не осталось. Тут следует уточнить: сомнений не осталось не только потому, что я нашёл пример и в $R^5$. Дело в том, что при самом построении примера чувствуется, что в $R^5$ происходит то же, что и в $R^4$ -- каких-то качественно новых сложностей не возникает, углы обзора всегда остаются, хотя и неуклонно сужаются. Легко видеть, что решение обладает некой симметрией (как и в $R^4$). Должны быть ещё и другие, внутренние, симметрии (см. моё сообщение выше), но я их здесь пока не разгадал. Ещё я предчувствую разницу между симметриями пространств чётных и нечётных размерностей, но это вряд ли может быть интересно за пределами танка :)

Но это всё лирика, а формула требует доказательства. И я почему-то думаю, что доказательство снизу будет найдено быстрее и проще, чем сверху.

[heptagon]

grizzly, я проверил Ваш пример. Поздравляю Вас, это просто фантастика!

[12d3]

grizzly

Заметил интересную штуку. Если взять ваши примеры для 4-х (тот, который "некрасивый") и 5-мерного пространства, посчитать у точек "центр масс", а потом расстояния от центра масс до этих точек, то расстояния получаются практически одинаковыми. Т.е. получается, что точки расположены на $(n-1)$-мерной гиперсфере. Более того, расстояния от каждой точки до ближайшего соседа тоже получаются примерно одинаковыми. Еще более того, в последнем примере у каждой точки ровно 4 соседа на расстоянии менее 1200.
Таким образом, построение таких примеров сильно смахивает на задачу о контактном числе, где тоже требуется распихать более-менее равномерно точки по гиперсфере.

[grizzly]

12d3
Очень интересные наблюдения. Я немного отдохну и тоже посмотрю на всякие внутренние симметрии. Кое-что из замеченного -- это артефакты поискового метода, но не всё. Например, привязка точек к углам 4D-куба сама по себе означает некую близость к условной гиперсфере, но если эта близость действительно окажется лучше ожидаемой, это даст что-то новое в понимании.

Заодно уточню, что попытки просто посмотреть, как мои программы и методы поиска будут вести себя в $\mathbb R^6$ ни к чему не привели -- там оно совсем не шевелится. Думаю, что построение других примеров вряд ли можно будет считать "разумной деятельностью" , но вот попытаться найти симметрии, понять и обобщить до уровня формулы было бы интересно.

[grizzly]

grizzly в сообщении #1231121 писал(а):

В этом раскладе не хватает ещё одной точки -- 17-й. ... И это не лечится мелкими подвижками -- нужно начинать строить всю конструкцию сначала. (А всего-то нужно было взять в самой первой строчке числа поменьше -- именно с этой точки я начинаю построение.)

Немного отдохнул и решил закончить, раз взялся. Добавил 17-ю точку -- строго по указанному выше сценарию (как я это знал -- сам удивляюсь :) Оказалось много проще, чем я думал. Пример под катом:

(ПРИМЕР 17 ТОЧЕК)

a=(  40,          40,          40,          40,         500    );
b=( 999,           1,           1,           1,           0    );
c=( 0.0001,    999.9999,      0.0001,      0.0001,      64.143   );
d=( 999.99999, 999.99999,        0,           0,        64.773   );
e=( 0,            0,        999.999989,     0.000009,   64.774   );
f=( 999.99999,    0,        999.999999,     0.000009,   64.776   );
g=( 0.000008,   999.99999,   999.999988,    0.000009,   64.918   );
h=( 999.999989,   1000,        1000,        0.000009,   64.775   );
                                                                                
k=( 0.000011,   0,         0,         999.999991,   64.775   );
l=( 999.999992, 0.00001,  0.000012,   999.999991,   64.918   );
m=( 0.00001,   1000,      0.000001,   999.999991,   64.776   );
n=( 1000,      1000,      0.000011,   999.999991,   64.774   );
o=( 0.00001,   0.00001,    1000,      1000,         64.773   );
p=( 999.9999,  0.0001,    999.9999,   999.9999,     64.143   );
q=( 1,         999,        999,       999,          0        );
r=( 960,       960,        960,       960,          500      );

s=( 455,       455,       455,         455,         -995   );

-- 05.07.2017, 17:17 --

heptagon
Буду благодарен, если проверите ещё и этот набор (не то чтоб я сомневался в своих программах, но перестраховаться в этом деле лишним не будет).

[12d3]

grizzly
Проверил, все верно.

[Deggial]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Математика (общие вопросы)»
Причина переноса: тема перенесена в более подходящий раздел

[a1981]

В архиве появился новый препринт московского школьника, с которого началась тема.
https://arxiv.org/pdf/1707.04829.pdfОценка снизу улучшена, хотя до высказываемой
уважаемым grizzly гипотезы не дотягивает

[grizzly]

a1981
Спасибо, очень интересная работа! На этот раз техника выглядит немного сложнее (это впечатление от первого просмотра; конечно я ещё не вникал в детали).

Хотелось бы сказать, что я тоже не сидел сложа руки в поисках закономерностей и явного алгоритма построения. Но так принято говорить только если получают какие-то результаты, а не просто тратят время Увы, существенных продвижений у меня нет. Поэтому меня особенно радуют очередные результаты Дмитрия -- вдруг они и мне чем-то помогут (как это было в прошлый раз, когда здесь всё завертелось :)

[grizzly]

Более-менее разобрался в последней работе Дмитрия. Да, он нашёл интересный способ раздваивать точки при каждом увеличении размерности. И в каком-то смысле он выжал из этого способа максимум, я думаю (начиная с $\mathbb R^2$ точки раздваиваются "жадным" алгоритмом). Я думаю, что для следующего прорыва нужно будет отказаться от "жадности" (но не от технических идей -- они ещё сослужат службу, наверно).

Я вложил один из своих инструментов (основной) поиска ОМ. Он работает в пространстве $\mathbb R^4$. Выкладываю как есть, без подробных описаний (минимум полезных комментариев есть внутри -- основное поле деятельности для пользователя между 225 и 290 строками). Инструмент вообще был написан "под себя" (программист не я, это всё группа поддержки) и предназначался для творческого поиска решений, поэтому в нём осели какие-то малопонятные механизмы -- на них можно не обращать внимания. Если кого-то заинтересует, постараюсь ответить на возникающие вопросы. Имеется также аналогичный вариант для $\mathbb R^5$, который ищет ОМ из $2^4$ точек, я его тоже выдам, если будет спрос :)

В дальнейшем планируется апгрейд с несколькими оптимизациями и украшением кода (сворачиванием циклов в рекурсии и т.п.). Я тогда это тоже выдам. Если вдруг кто-то при использовании сможет добиться лучшей эффективности, просьба делиться.

-- 31.07.2017, 10:54 --

Это всё работает миллисекунды. А значит в 80-х вполне реально было посчитать на тех компах. Очень странно, что столько людей тогда прошло мимо.

[Sender]

grizzly в сообщении #1236964 писал(а):

сворачиванием циклов в рекурсии и т.п.

Вот как раз сворачивание циклов в рекурсии может негативно сказаться на быстродействии, как мне кажется.