<p>Let <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11425_2024_2384_Article_IEq1.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="57" /> </InlineMediaObject> <EquationSource Format="TEX">\(\alpha({\mathbb F}_{q}^{d}, p)\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mi>α</mi> <mo stretchy="false">(</mo> <msubsup> <mrow> <mrow> <mi mathvariant="double-struck">F</mi> </mrow> </mrow> <mrow> <mi>q</mi> </mrow> <mrow> <mi>d</mi> </mrow> </msubsup> <mo>,</mo> <mi>p</mi> <mo stretchy="false">)</mo> </math></EquationSource> </InlineEquation> denote the maximum size of a general position set in a <i>p</i>-random subset of <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11425_2024_2384_Article_IEq2.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mathbb F}_{q}^{d}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msubsup> <mrow> <mrow> <mi mathvariant="double-struck">F</mi> </mrow> </mrow> <mrow> <mi>q</mi> </mrow> <mrow> <mi>d</mi> </mrow> </msubsup> </math></EquationSource> </InlineEquation>. We determine the order of magnitude of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11425_2024_2384_Article_IEq3.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="57" /> </InlineMediaObject> <EquationSource Format="TEX">\(\alpha({\mathbb F}_{q}^{2}, p)\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mi>α</mi> <mo stretchy="false">(</mo> <msubsup> <mrow> <mrow> <mi mathvariant="double-struck">F</mi> </mrow> </mrow> <mrow> <mi>q</mi> </mrow> <mrow> <mn>2</mn> </mrow> </msubsup> <mo>,</mo> <mi>p</mi> <mo stretchy="false">)</mo> </math></EquationSource> </InlineEquation> up to polylogarithmic factors for all possible values of <i>p</i>, improving the previous results obtained by Roche-Newton and Warren (2022) and Bhowmick and Roche-Newton (2024). For <i>d</i> ⩾ 3, we prove upper bounds for <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11425_2024_2384_Article_IEq1.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="57" /> </InlineMediaObject> <EquationSource Format="TEX">\(\alpha({\mathbb F}_{q}^{d}, p)\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mi>α</mi> <mo stretchy="false">(</mo> <msubsup> <mrow> <mrow> <mi mathvariant="double-struck">F</mi> </mrow> </mrow> <mrow> <mi>q</mi> </mrow> <mrow> <mi>d</mi> </mrow> </msubsup> <mo>,</mo> <mi>p</mi> <mo stretchy="false">)</mo> </math></EquationSource> </InlineEquation> that are essentially tight within certain ranges for <i>p</i>. We establish the upper bound <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11425_2024_2384_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="60" /> </InlineMediaObject> <EquationSource Format="TEX">\(2^{{(1+o(1))}_{q}}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msup> <mn>2</mn> <mrow> <msub> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>o</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> <mrow> <mi>q</mi> </mrow> </msub> </mrow> </msup> </math></EquationSource> </InlineEquation> for the number of general position sets in <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11425_2024_2384_Article_IEq2.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mathbb F}_{q}^{d}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msubsup> <mrow> <mrow> <mi mathvariant="double-struck">F</mi> </mrow> </mrow> <mrow> <mi>q</mi> </mrow> <mrow> <mi>d</mi> </mrow> </msubsup> </math></EquationSource> </InlineEquation>, which matches the trivial lower bound 2<sup><i>q</i></sup> asymptotically in the exponent. We also refine this counting result by proving an asymptotically tight (in the exponent) upper bound for the number of general position sets with a fixed size. The latter result for <i>d</i> = 2 improves the result of Roche-Newton and Warren (2022). Our proofs are grounded in the hypergraph container method. In addition, for <i>d</i> = 2, we also leverage the pseudorandomness of the point-line incidence graph of <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11425_2024_2384_Article_IEq7.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mathbb F}_{q}^{2}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msubsup> <mrow> <mrow> <mi mathvariant="double-struck">F</mi> </mrow> </mrow> <mrow> <mi>q</mi> </mrow> <mrow> <mn>2</mn> </mrow> </msubsup> </math></EquationSource> </InlineEquation>.</p>

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

Random Turán and counting results for general position sets over finite fields

  • Yaobin Chen,
  • Xizhi Liu,
  • Jiaxi Nie,
  • Ji Zeng

摘要

Let \(\alpha({\mathbb F}_{q}^{d}, p)\) α ( F q d , p ) denote the maximum size of a general position set in a p-random subset of \({\mathbb F}_{q}^{d}\) F q d . We determine the order of magnitude of \(\alpha({\mathbb F}_{q}^{2}, p)\) α ( F q 2 , p ) up to polylogarithmic factors for all possible values of p, improving the previous results obtained by Roche-Newton and Warren (2022) and Bhowmick and Roche-Newton (2024). For d ⩾ 3, we prove upper bounds for \(\alpha({\mathbb F}_{q}^{d}, p)\) α ( F q d , p ) that are essentially tight within certain ranges for p. We establish the upper bound \(2^{{(1+o(1))}_{q}}\) 2 ( 1 + o ( 1 ) ) q for the number of general position sets in \({\mathbb F}_{q}^{d}\) F q d , which matches the trivial lower bound 2q asymptotically in the exponent. We also refine this counting result by proving an asymptotically tight (in the exponent) upper bound for the number of general position sets with a fixed size. The latter result for d = 2 improves the result of Roche-Newton and Warren (2022). Our proofs are grounded in the hypergraph container method. In addition, for d = 2, we also leverage the pseudorandomness of the point-line incidence graph of \({\mathbb F}_{q}^{2}\) F q 2 .