# Elementary counting inequality in a finite field

Let $\Bbb F$ be a finite field, let $A \subset \Bbb F$, and let $f: \Bbb F \to \Bbb N$ be defined by $f(x)$ = the number of elements $a \in A$ for which $\frac xa \in A$. Then $\sum _{x \in \Bbb F}f(x)^2 \leq |A|^3$.

This can be seen directly to be true when $A$ is empty or a singleton. The context is somewhat complicated, where it was expressed as indicator functions, and this formulation looks more convenient. The obvious upper bound is $|\Bbb F| |A|^2$ which is too weak.

EDIT

A harder proof is the following: We note that $\frac 1 {|A|}f=\Bbb E_{a \in A}1_{aA}$, where $1_{aA}$ is the indicator function that says for every $x$ whether $\exists b \in A:x=ab$. Then we compute $$\Bbb E_{x \in \Bbb F} (\frac 1 {|A|}f)^2 = ||(\Bbb E_{a \in A}1_{aA})||^2 \leq (\Bbb E _{a \in A}||1_{aA}||_{L^2}\;)^2 \stackrel{1_{aA}=1_{aA}^2}{=}(\Bbb E _{a \in A}\sqrt{\Bbb E_{x \in \Bbb F }1_{aA}(x)}\;)^2 = \frac {|A|}{|\Bbb F|}$$

Where the inequality is the triangle inequality in $L^2$ (Minkowski's inequality), and the last equality is since $\sum_{x \in \Bbb F} 1_{aA}(x) = |A|$.

$$\sum_{x \in \mathbb F} f(x) = |A|^2$$
Therefore, we are led to study the constrained optimization problem where $\sum X_n = r^2$, $0 \leq X_i \leq r$, and we are trying to maximize $\sum X_n^2$. (We study this problem where the $X_i$ are allowed to be real, not just natural, as this makes our task easier. This generalization does not affect the final result.) First, assume that there are some $X_i, X_j$ with $i \neq j$ such that $0 < X_i < X_j < r$. Then, by picking $\epsilon > 0$ small enough and replacing $X_i, X_j$ with $X_i - \epsilon, X_j + \epsilon$ respectively, we increase the value of the expression $\sum X_n^2$. Therefore, the maximum must occur when all but one of the $X_i$ are either $0$ or $r$. However, in this case, it is easy to check that the remaining unknown variable can only be a nonnegative integer multiple of $r$, and the inequalities force it to be either $0$ or $r$. Therefore, the maximum occurs when all of the $X_i$ are either $0$ or $r$, and the constraint implies that exactly $r$ of them must be equal to $r$, and the others must be equal to $0$. Thus, at the maximum, we have
$$\sum X_n^2 = \sum_{k=1}^r r^2 = r^3$$