論文の概要: Optimizing Explicit Unit-Distance Lower-Bound Certificates

• arxiv url: http://arxiv.org/abs/2606.03419v2
• Date: Wed, 03 Jun 2026 04:25:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-04 17:40:41.630089
• Title: Optimizing Explicit Unit-Distance Lower-Bound Certificates
• Title（参考訳）: 明示的単位距離下界証明書の最適化
• Authors: Michael T. M. Emmerich,
• Abstract要約: この報告はSawinの非線形整数最適化問題から始まり、オープンソースのPython検証パイプラインを開発する。 パイプラインは、最初にサウィンが公表したパラメータ選択を再現して検証され、その後、計算的に改善された証明書に適用される。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The 2026 disproof of Erdős's unit-distance conjecture and Sawin's subsequent explicit quantitative refinement show that the maximum number $u(n)$ of unit distances among $n$ planar points can exceed $n^{1+\varepsilon}$ for a fixed positive $\varepsilon$. Sawin's explicit bound gives more than $n^{1.014}$ unit distances for arbitrarily large $n$ and exposes integer parameters whose choice is not fully optimized. This report starts from Sawin's nonlinear integer optimization problem and develops an open-source Python verification pipeline. The pipeline is first validated by reproducing Sawin's published parameter choice and is then applied to computationally improved certificates. We optimize and verify certificates involving sets of primes $T$ and $S_Q$, integer multiplicities $k(p)$, and a rationally encoded real parameter $R$. The implementation is deliberately lean, so that all results can be replicated on standard hardware and the procedures can be extended. We compare a deterministic greedy heuristic, a tailored integer evolution strategy with two-sided geometric, or discrete-Laplace, integer mutation and repair operators for number-theoretic feasibility, and a two-parent discrete-recombination variant. Four certificate levels are reported: Sawin's published example with $δ=0.0141144286784982\ldots$, a greedy certificate with $δ=0.0151718056372133\ldots$, a tailored integer evolution strategy certificate with $R=6672416/100000$ and $δ=0.0152616610684193\ldots$, and a recombination variant with the same $R$ and $δ=0.0152628688170072\ldots$. Consequently, the best current certificate supports the cautious statement $u(n)>n^{1.0152}$ for arbitrarily large $n$. Beyond this unit-distance application, the work illustrates how randomized optimization heuristics can improve explicit certificates in pure mathematics and combinatorial geometry.
• Abstract（参考訳）: 2026年のエルデシュの単位距離予想と、サウィンのその後の明示的な量的洗練は、固定正の$\varepsilon$に対して、$n$平面点の間の単位距離の最大数$u(n)$が$n^{1+\varepsilon}$を超えることを示した。 サウィンの明示的な境界は、任意の大きさの$n$に対して$n^{1.014}$単位距離を与え、完全に最適化されていない整数パラメータを公開する。 この報告はSawinの非線形整数最適化問題から始まり、オープンソースのPython検証パイプラインを開発する。 パイプラインは、最初にサウィンが公表したパラメータ選択を再現して検証され、その後、計算的に改善された証明書に適用される。 我々は、素数の集合である$T$と$S_Q$、整数乗法$k(p)$、合理的にエンコードされた実パラメータ$R$を含む証明書を最適化し、検証する。 実装は意図的にリーンなので、すべての結果を標準ハードウェア上で複製することができ、手順を拡張できます。 決定論的グリーディヒューリスティック(deterministic greedy Heuristic)と,2辺の幾何あるいは離散ラプラス(disceptive-Laplace)と,整数変異と補修演算子(integer mutation and repair operator for number-theoretic feasibility)を比較した。 Sawinの発行した$δ=0.0141144286784982\ldots$、$δ=0.0151718056372133\ldots$、$R=6672416/100000$と$δ=0.0152616616684193\ldots$、$R$と$δ=0.0152628688170072\ldots$の組換えである。 したがって、最も優れた現在の証明書は、任意に大きな$n$に対して$u(n)>n^{1.0152}$という慎重な文をサポートする。 この単位距離応用の他に、この研究は、ランダム化された最適化ヒューリスティックスが純粋数学と組合せ幾何学における明示的な証明をいかに改善できるかを描いている。

関連論文リスト

• Parameter-free Algorithms for the Stochastically Extended Adversarial Model [59.81852138768642]
  拡張逆数(SEA)モデルの既存のアプローチは、ドメインの直径$D$や損失関数のリプシッツ定数$G$といった問題固有のパラメータの事前知識を必要とする。 パラメータを不要にするためにOptimistic Online Newton Step (OONS) アルゴリズムを利用するパラメータフリー手法を開発した。
  論文  参考訳（メタデータ） (2025-10-06T10:53:37Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  この仮定は、収束とより微細な結果には必要ないことが初めて示される。 標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。 数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-05-28T05:11:05Z)
• Efficient, direct compilation of SU(N) operations into SNAP & Displacement gates [0.0]
  Map $Phi$は、$d$次元のユニタリを直接SNAPと変位ゲートのシーケンスにコンパイルする機能を提供する。 計算回路上の誤差は各回転を$m$$theta/m$回転に分割することで任意に小さくすることができる。
  論文  参考訳（メタデータ） (2023-07-21T20:58:17Z)
• Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
  任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。 この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
  論文  参考訳（メタデータ） (2023-03-06T17:54:33Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
  論文  参考訳（メタデータ） (2022-03-18T18:50:52Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• High-Order Oracle Complexity of Smooth and Strongly Convex Optimization [31.714928102950584]
  非常に滑らかな (Lipschitz $k$-thorder derivative) 関数と強い凸関数を$k$-thorder Oracleへの呼び出しによって最適化する複雑性を考える。 我々は、関数を正確に$epsilon$まで最適化するために、固定された$k$で最悪の場合のオラクルの複雑さが$leftの順序にあることを証明している。
  論文  参考訳（メタデータ） (2020-10-13T19:18:15Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Convergence of Sparse Variational Inference in Gaussian Processes Regression [29.636483122130027]
  計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
  論文  参考訳（メタデータ） (2020-08-01T19:23:34Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。