3
$\begingroup$

Let $F$ be a finite field of odd order n. Let $H$ be the subgroup of $F^\times$ composed of the nonzero squares. What can we say about $|H\cap (H+c)|$ given $c\in F$? The expected value of $|H\cap (H+c)|$ is roughly $n/4$ when $c$ is random. But I wonder what the distribution looks like. For example, Is there an infinite family of finite fields for which $|H\cap (H+c)|$ deviates from its expectation dramatically, say by a constant multiplicative factor?

More generally, how about the intersection of a multiple number of additive shifts, like $|H\cap (H+c_1)\cap (H+c_2)\cap\cdots\cap (H+c_m)|$?

$\endgroup$
0

2 Answers 2

3
$\begingroup$

In fields of prime order, factoring the difference of squares shows that the number of solutions to $x^2=y^2+c$ is what you expect it to be, from which it follows the intersection $H\cap (H+c)$ has size about what you expect. For triple intersections such as $H\cap (H+1)\cap (H+2)$, one there is an elementary argument for certain values of $p$, but not others (in this example, for $p=3,7\pmod 8$). In general you will need estimate the character sum $$\sum_x \chi(x(x+c_1)(x+c_2)\dotsb(x+c_m))$$ where $\chi$ is the Legendre symbol modulo $p$. This can be estimated by invoking Riemann hypothesis for curves.

By the way, if $H$ were a small subgroup of $ F* $ (of size $n^{1-\epsilon}$), then the sum-product estimates show that the intersection $|H\cap (H+c)|$ can never be large. See for example, this paper for a related problem of estimating the product of $H$ and $H+c$.

The following is wrong since (H+c) is not closed under multiplication:

One can get the result for the intersection by using Ruzsa's triangle inequality. Namely, $$|H(H+c)|\leq \frac{|H(H\cap (H+c))||(H+c)(H\cap (H+c))|}{|(H\cap (H+c))|}\leq \frac{|H|^2}{|(H\cap (H+c))|}$$.

$\endgroup$
2
$\begingroup$

Fix a positive integer $e$, let $n$ be a prime power congruent to 1 modulo $e$, let $F$ be the field of $n$ elements, let $H$ be the subgroup of index $e$ in the multiplicative group of $F$. Then the study of the size of $H\cap(H+c)$ is called $\it cyclotomy$, it goes back to Gauss (for the cases $e=2,3,4$ and $n$ a prime), there's a book by Tom Storer, and many papers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.