<p>We study subsets of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq4.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathbb {F}_p^n\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>p</mi> <mi>n</mi> </msubsup> </math></EquationSource> </InlineEquation> that do not contain progressions of length <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq5.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>. We denote by <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq6.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">\(r_k(\mathbb {F}_p^n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>r</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>p</mi> <mi>n</mi> </msubsup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> the cardinality of such subsets containing a maximal number of elements. In this paper we focus on the case <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq7.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">\(k=p\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mi>p</mi> </mrow> </math></EquationSource> </InlineEquation> and therefore sets containing no full line. A&#xa0;trivial lower bound <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq8.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="126" /> </InlineMediaObject> <EquationSource Format="TEX">\(r_p(\mathbb {F}_p^n)\ge (p-1)^n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>r</mi> <mi>p</mi> </msub> <mrow> <mo stretchy="false">(</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>p</mi> <mi>n</mi> </msubsup> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mi>n</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> is achieved by a hypercube of side length <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq9.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(p-1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and it is known that equality holds for <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="77" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\in \{1,2\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>∈</mo> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. We will however show that <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq11.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="205" /> </InlineMediaObject> <EquationSource Format="TEX">\(r_p(\mathbb {F}_p^3)\ge (p-1)^3+p-2\sqrt{p}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>r</mi> <mi>p</mi> </msub> <mrow> <mo stretchy="false">(</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>p</mi> <mn>3</mn> </msubsup> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mn>3</mn> </msup> <mo>+</mo> <mi>p</mi> <mo>-</mo> <mn>2</mn> <msqrt> <mi>p</mi> </msqrt> </mrow> </math></EquationSource> </InlineEquation>, which is the first improvement in the three-dimensional case that is increasing in <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq12.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(p\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>p</mi> </math></EquationSource> </InlineEquation>. We will also give the upper bound <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq13.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="246" /> </InlineMediaObject> <EquationSource Format="TEX">\(r_p(\mathbb {F}_p^{3})\le p^3-2p^2-(\sqrt{2}-1)p+2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>r</mi> <mi>p</mi> </msub> <mrow> <mo stretchy="false">(</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mi>p</mi> <mn>3</mn> </msubsup> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <msup> <mi>p</mi> <mn>3</mn> </msup> <mo>-</mo> <mn>2</mn> <msup> <mi>p</mi> <mn>2</mn> </msup> <mo>-</mo> <mrow> <mo stretchy="false">(</mo> <msqrt> <mn>2</mn> </msqrt> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mi>p</mi> <mo>+</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> as well as generalizations for higher dimensions. Finally, we present some bounds for individual <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq14.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(p\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>p</mi> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq15.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>, in particular <InlineEquation ID="IEq16"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq16.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="83" /> </InlineMediaObject> <EquationSource Format="TEX">\(r_5(\mathbb {F}_5^{3})\ge 70\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>r</mi> <mn>5</mn> </msub> <mrow> <mo stretchy="false">(</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mn>5</mn> <mn>3</mn> </msubsup> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mn>70</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq17"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq17.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="91" /> </InlineMediaObject> <EquationSource Format="TEX">\(r_7(\mathbb {F}_7^{3})\ge 225\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>r</mi> <mn>7</mn> </msub> <mrow> <mo stretchy="false">(</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mn>7</mn> <mn>3</mn> </msubsup> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mn>225</mn> </mrow> </math></EquationSource> </InlineEquation> which can be used to give the asymptotic lower bound <InlineEquation ID="IEq18"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq18.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">\(4.121^n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>4</mn> <mo>.</mo> <msup> <mn>121</mn> <mi>n</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq19"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq19.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">\(r_5(\mathbb {F}_5^{n})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>r</mi> <mn>5</mn> </msub> <mrow> <mo stretchy="false">(</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mn>5</mn> <mi>n</mi> </msubsup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq20"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq20.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">\(6.082^n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>6</mn> <mo>.</mo> <msup> <mn>082</mn> <mi>n</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq21"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10998_2024_617_Article_IEq21.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">\(r_7(\mathbb {F}_7^{n})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>r</mi> <mn>7</mn> </msub> <mrow> <mo stretchy="false">(</mo> <msubsup> <mi mathvariant="double-struck">F</mi> <mn>7</mn> <mi>n</mi> </msubsup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

Maximal line-free sets in \(\mathbb {F}_p^n\)

  • Christian Elsholtz,
  • Jakob Führer,
  • Erik Füredi,
  • Benedek Kovács,
  • Péter Pál Pach,
  • Dániel Gábor Simon,
  • Nóra Velich

摘要

We study subsets of \(\mathbb {F}_p^n\) F p n that do not contain progressions of length \(k\) k . We denote by \(r_k(\mathbb {F}_p^n)\) r k ( F p n ) the cardinality of such subsets containing a maximal number of elements. In this paper we focus on the case \(k=p\) k = p and therefore sets containing no full line. A trivial lower bound \(r_p(\mathbb {F}_p^n)\ge (p-1)^n\) r p ( F p n ) ( p - 1 ) n is achieved by a hypercube of side length \(p-1\) p - 1 and it is known that equality holds for \(n\in \{1,2\}\) n { 1 , 2 } . We will however show that \(r_p(\mathbb {F}_p^3)\ge (p-1)^3+p-2\sqrt{p}\) r p ( F p 3 ) ( p - 1 ) 3 + p - 2 p , which is the first improvement in the three-dimensional case that is increasing in \(p\) p . We will also give the upper bound \(r_p(\mathbb {F}_p^{3})\le p^3-2p^2-(\sqrt{2}-1)p+2\) r p ( F p 3 ) p 3 - 2 p 2 - ( 2 - 1 ) p + 2 as well as generalizations for higher dimensions. Finally, we present some bounds for individual \(p\) p and \(n\) n , in particular \(r_5(\mathbb {F}_5^{3})\ge 70\) r 5 ( F 5 3 ) 70 and \(r_7(\mathbb {F}_7^{3})\ge 225\) r 7 ( F 7 3 ) 225 which can be used to give the asymptotic lower bound \(4.121^n\) 4 . 121 n for \(r_5(\mathbb {F}_5^{n})\) r 5 ( F 5 n ) and \(6.082^n\) 6 . 082 n for \(r_7(\mathbb {F}_7^{n})\) r 7 ( F 7 n ) .