OpenAI réfute la conjecture d’Erdős sur la distance unitaire

par Ed Pegg
Article original
Le problème des distances unitaires d’Erdős demande quel est le plus grand nombre u(n) possible de distances unitaires parmi n points dans le plan. Cela revient à trouver des graphes de distance unitaire de densité maximale.
Une annonce récente d’OpenAI porte sur le problème asymptotique : l’ancienne conjecture n^(1+o(1)) est fausse.
Dans la formulation d’Erdős, il a fondé sa conjecture sur la densité croissante des graphes unitaires issus d’une grille carrée.
In[]:=
units=Select[Tuples[Tuples[Range[8]/5,{2}],{2}],RootReduce[EuclideanDistance@@#]==1&];​​Graphics[Line/@units];​​GraphData[{"Fiveleaper",{8,8}}]
Out[]=
Ce qui précède est fondé sur le fait que 25 est la somme de 2 carrés de plus d’une manière.
In[]:=
PowersRepresentations[25,2,2]
Out[]=
{{0,5},{3,4}}
Étonnamment, ce graphe, le graphe « cinq sauts-8 », est un graphe quartique. Si nous passons à des valeurs plus élevées, nous pouvons obtenir des nombres plus denses en diagonales (OEIS A000446).
In[]:=
PowersRepresentations[325,2,2]
Out[]=
{{1,18},{6,17},{10,15}}
In[]:=
PowersRepresentations[1105,2,2]
Out[]=
{{4,33},{9,32},{12,31},{23,24}}
In[]:=
PowersRepresentations[27625,2,2]
Out[]=
{{20,165},{27,164},{45,160},{60,155},{83,144},{88,141},{101,132},{115,120}}
Cependant, dans les graphes à distance unitaire de densité maximale, nous ne voyons aucun signe de convergence vers des grilles carrées. Au lieu de cela, des graphes plus étranges fondés sur des constructions algébriques prédominent.
In[]:=
Row[Table[GraphData[{"MaximallyDenseUnitDistance",{21,k}}],{k,1,5}]]
Out[]=
On pourrait résumer l’article d’OpenAI en disant que « les constructions algébriques l’emportent ».
Alors, qu’est-ce qu’une construction algébrique ? En voici une fondée sur les étoiles unitaires 7|1, 7|2 et 7|3. Elles s’emboîtent parfaitement ensemble.
In[]:=
GraphData[{"BracedHeptagon",{42,1}}]
Out[]=
Voici une construction plus étrange fondée sur le rapport superdoré, la racine réelle de
3
ψ
=
2
ψ
+1, ψ=1.46557... . Tous les nombres ici sont des distances et représentent des puissances de
1/2
ψ
. Les lignes horizontales sont des distances
0
ψ
,
1
ψ
et
4
ψ
. Il s’agit donc d’un graphe complet K7 donné comme un ensemble de points, sans que trois points ne soient alignés, et avec toutes les distances étant des puissances entières de la même constante. Peut-on faire cela avec 8 points ? Au fait, j’appelle cela le diamant superdoré.
Out[]=
Quoi qu’il en soit, les possibilités des grilles algébriques sont à peine explorées. Les graphes maximaux pour 18 points proviennent d’une convergence de deux ensembles différents de figures algébriques.
In[]:=
Grid[Partition[Table[GraphData[{"MaximallyDenseUnitDistance",{18,k}}],{k,1,16}],4]]
Out[]=

CITER CE NOTEBOOK