7
$\begingroup$

Let $G \subseteq \mathbb F_p^*$ be a subgroup. Then $G$ is called almost trivial if $G \cap (2-G)$ consists of the element 1.

Then I am wondering how big $G$ can be in terms of $p$. If $G$ is a random set containing 1 then according to the birthday paradox one expects that $G$ and $2-G$ have nontrivial intersection as soon as $\#G \gg \sqrt p$.

I am wondering if maybe one could prove that all almost trivial subgroups of $\mathbb F_p^*$ have size at most $\tilde O(\sqrt p)$.

Or if a $\sqrt p$ up to log factors bound is out of reach, I was wondering if there is $1/2 < \epsilon < 1$ and some constant $c$ such that for all almost trivial groups we have $\#G < cp^\epsilon$.

I did some numeric experimentation by finding the largest almost trivial subgroup of $\mathbb F_p^*$ for all p < 80000. And the largest ratio that I could find for $\frac {\#G}{\sqrt p}$ was $\frac {884}{\sqrt {41549}} = 4.3368\ldots$ because $\mathbb F_{41549}$ contains an almost trivial subgroup of order 884, so a square root (possibly up to log factors) bound seams reasonable.

P.S. The notion of being almost trivial is based on the notion of almost rational in the paper Almost rational torsion points on semistable elliptic curves by Frank Calegari.

$\endgroup$
2
  • 4
    $\begingroup$ Every subgroup contains 1 so how can it be 2-complementary? $\endgroup$
    – Squala
    Commented Dec 24, 2021 at 23:08
  • 1
    $\begingroup$ Sorry, my mistake. I rewrote the question significantly to correct the mistake you highlight. For some reason I had the wrong notion of "trivial intersection" in the back of my mind. Strangely enough I did explicitly exclude the element 1 in the code that I wrote. $\endgroup$ Commented Dec 24, 2021 at 23:27

1 Answer 1

13
$\begingroup$

If we let $S$ be the set of characters of $\mathbb F_p^\times$ trivial on $G$ then $$\sum_{\chi \in S} \chi(g) = \begin{cases} \frac{p-1}{|G|} & g\in G \\ 0 & g\notin G \end{cases}$$

so $$\sum_{\chi_1,\chi_2\in S} \sum_{ g \in \mathbb F_p \setminus \{0,1,2\} } \chi_1(g) \chi_2(2-g) = 0$$ if $G$ is almost trivial.

Now if $\chi_1 =\chi_2=1$ then $\sum_{ g \in \mathbb F_p \setminus \{0,1,2\} } \chi_1(g) \chi_2(2-g)=p-3$ and otherwise, by the bound for Jacobi sums, $\left| \sum_{ g \in \mathbb F_p \setminus \{0,1,2\} } \chi_1(g) \chi_2(2-g) \right| \leq \sqrt{p}+1 $.

Thus, if $G$ is almost trivial then $p-3 \leq ( ((p-1)/|G|)^2-1) (\sqrt{p}+1)$, or $p \leq c^2 p^{5/2} / |G|^2$ for a constant $c$, meaning $|G| \leq c p^{3/4}$, answering the weaker form of your question.

$\endgroup$
2
  • $\begingroup$ Are there typos in the inequalities in your last line, especially in terms of the direction of the inequality? It seems to me that the first inequality should read $p-3 \leqslant (m^2 - 1)(\sqrt{p}+1)$ where $m = (p-1)/|G|$? $\endgroup$ Commented Dec 25, 2021 at 1:09
  • 1
    $\begingroup$ @AnuragSahay Yes, good point, fixed or at least improved. $\endgroup$
    – Will Sawin
    Commented Dec 25, 2021 at 2:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .