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.


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|$.


There is a fairly elementary proof of this. First, observe that

$$ \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 $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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