<p>We prove that the diameter of a Sidon set (also known as a Babcock sequence, Golomb ruler, or <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2024_1499_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\(B_2\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>B</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> set) with <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2024_1499_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(k\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation> elements is at least <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2024_1499_Article_IEq3.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="129" /> </InlineMediaObject> <EquationSource Format="TEX">\(k^2-b k^{3/2}-O(k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>k</mi> <mn>2</mn> </msup> <mo>-</mo> <mi>b</mi> <msup> <mi>k</mi> <mrow> <mn>3</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo>-</mo> <mi>O</mi> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> where <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2024_1499_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="84" /> </InlineMediaObject> <EquationSource Format="TEX">\(b\le 1.96365\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>b</mi> <mo>≤</mo> <mn>1.96365</mn> </mrow> </math></EquationSource> </InlineEquation>, a comparatively large improvement on past results. Equivalently, a Sidon set with diameter <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2024_1499_Article_IEq5.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> </InlineEquation> has at most <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2024_1499_Article_IEq6.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="184" /> </InlineMediaObject> <EquationSource Format="TEX">\(n^{1/2}+0.98183n^{1/4}+O(1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>n</mi> <mrow> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mn>0.98183</mn> <msup> <mi>n</mi> <mrow> <mn>1</mn> <mo stretchy="false">/</mo> <mn>4</mn> </mrow> </msup> <mo>+</mo> <mi>O</mi> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> elements. The proof is conceptually simple but very computationally intensive, and the proof uses substantial computer assistance. We also provide a proof of <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2024_1499_Article_IEq7.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="84" /> </InlineMediaObject> <EquationSource Format="TEX">\(b\le 1.99058\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>b</mi> <mo>≤</mo> <mn>1.99058</mn> </mrow> </math></EquationSource> </InlineEquation> that can be verified by hand, which still improves on past results. Finally, we prove that <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2024_1499_Article_IEq8.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(g\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>g</mi> </math></EquationSource> </InlineEquation>-thin Sidon sets (aka <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2024_1499_Article_IEq9.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(g\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>g</mi> </math></EquationSource> </InlineEquation>-Golomb rulers) with <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2024_1499_Article_IEq10.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(k\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation> elements have diameter at least <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2024_1499_Article_IEq11.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="220" /> </InlineMediaObject> <EquationSource Format="TEX">\(g^{-1} k^2 - (2-\varepsilon)g^{-1}k^{3/2} - O(k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>g</mi> <mrow> <mo>-</mo> <mn>1</mn> </mrow> </msup> <msup> <mi>k</mi> <mn>2</mn> </msup> <mo>-</mo> <mrow> <mo stretchy="false">(</mo> <mn>2</mn> <mo>-</mo> <mi>ε</mi> <mo stretchy="false">)</mo> </mrow> <msup> <mi>g</mi> <mrow> <mo>-</mo> <mn>1</mn> </mrow> </msup> <msup> <mi>k</mi> <mrow> <mn>3</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo>-</mo> <mi>O</mi> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, with <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10474_2024_1499_Article_IEq12.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="101" /> </InlineMediaObject> <EquationSource Format="TEX">\(\varepsilon\ge 0.0062g^{-4}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ε</mi> <mo>≥</mo> <mn>0.0062</mn> <msup> <mi>g</mi> <mrow> <mo>-</mo> <mn>4</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the diameter of finite Sidon sets

  • D. Carter,
  • Z. Hunter,
  • K. O’Bryant

摘要

We prove that the diameter of a Sidon set (also known as a Babcock sequence, Golomb ruler, or \(B_2\) B 2 set) with \(k\) k elements is at least \(k^2-b k^{3/2}-O(k)\) k 2 - b k 3 / 2 - O ( k ) where \(b\le 1.96365\) b 1.96365 , a comparatively large improvement on past results. Equivalently, a Sidon set with diameter \(n\) n has at most \(n^{1/2}+0.98183n^{1/4}+O(1)\) n 1 / 2 + 0.98183 n 1 / 4 + O ( 1 ) elements. The proof is conceptually simple but very computationally intensive, and the proof uses substantial computer assistance. We also provide a proof of \(b\le 1.99058\) b 1.99058 that can be verified by hand, which still improves on past results. Finally, we prove that \(g\) g -thin Sidon sets (aka \(g\) g -Golomb rulers) with \(k\) k elements have diameter at least \(g^{-1} k^2 - (2-\varepsilon)g^{-1}k^{3/2} - O(k)\) g - 1 k 2 - ( 2 - ε ) g - 1 k 3 / 2 - O ( k ) , with \(\varepsilon\ge 0.0062g^{-4}\) ε 0.0062 g - 4 .