Distribution of power residues over shifted subfields and maximal cliques in generalized Paley graphs

Abstract

We derive an asymptotic formula for the number of solutions in a given subfield to certain system of equations over finite fields. As an application, we construct new families of maximal cliques in generalized Paley graphs. Given integers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d greater-than-or-equal-to 2"> <mml:semantics> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">d\ge 2</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="q identical-to 1 left-parenthesis normal m normal o normal d d right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>q</mml:mi> <mml:mo>≡</mml:mo> <mml:mn>1</mml:mn> <mml:mtext> </mml:mtext> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">m</mml:mi> <mml:mi mathvariant="normal">o</mml:mi> <mml:mi mathvariant="normal">d</mml:mi> </mml:mrow> <mml:mtext> </mml:mtext> <mml:mi>d</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">q \equiv 1\ (\mathrm {mod}\ d)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, we show that for each positive integer <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"> <mml:semantics> <mml:mi>m</mml:mi> <mml:annotation encoding="application/x-tex">m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> such that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r a d left-parenthesis m right-parenthesis bar r a d left-parenthesis d right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>rad</mml:mi> <mml:mo>⁡</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>m</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>∣</mml:mo> <mml:mi>rad</mml:mi> <mml:mo>⁡</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>d</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\operatorname {rad}(m) \mid \operatorname {rad}(d)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, there are maximal cliques of size approximately <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="q slash m"> <mml:semantics> <mml:mrow> <mml:mi>q</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>m</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">q/m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"> <mml:semantics> <mml:mi>d</mml:mi> <mml:annotation encoding="application/x-tex">d</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-Paley graph defined on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper F Subscript q Sub Superscript d"> <mml:semantics> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">F</mml:mi> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>q</mml:mi> <mml:mi>d</mml:mi> </mml:msup> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">\mathbb {F}_{q^d}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We also confirm a conjecture of Goryainov, Shalaginov, and Yip on the maximality of certain cliques in generalized Paley graphs, as well as an analogous conjecture of Goryainov for Peisert graphs.

Locations

• Proceedings of the American Mathematical Society - View
• arXiv (Cornell University) - View - PDF