MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a (suppose prime order) group G, for any two partions $\{A_i\}_{i\in I}$ and $\{B_j\}_{j\in J}$ of the group $G$ consider the following quantity $$ E = \sum\limits_{i \in I,j \in J} \max_{g} r_{A_i,B_j}(g) $$ Here $r_{A,B}(g)$ denotes (as usual) the number of pairs $a\in A, b\in B$ satisfying $a+b=g$.

Question: Is it possible to come up with an upper bound on $E$ in terms of only cardinalities $|I|, |J|, |G|$)? Trivially we have $E \leqslant |G|\min(|I|,|J|)$

I have no idea how to attack this problem. This is not a one question about particular estimate but an optimization problem that looks hard. The trivial bound is essentiale tight if $G = \mathbb{Z}_p \times \mathbb{Z}_q$ (take families $A_i$ and $B_j$ to be the cosets one of subgroups. That's why I would like to assume that the order is prime and want to exploit somehow the structure of $G$....

Motivation This problem refers to some problem concerning secret sharing. Suppose, that we have two functions $f,g$ on a group $G$. Let $X,Y$ be uniform and independent on $G$. If $A_i$ and $B_j$ are respectively, the preimages of $f$ and $g$ then the quanitity $E$ express the probability that we can guess $X+Y$ given $f(X),g(Y)$.

share|cite|improve this question

The trivial upper bound is in some sense best possible. Suppose I choose both partitions to consist of $p/N$ intervals of length $N$, say $[1,N],[N+1,2N],[(p-1)/N,p]$ (with a small error). Now given any pair of these intervals, $[a,a+N]$ and $[b,b+N]$, the element $a+b+N$ has about $N$ representations as $(a+k)+(b+N-k)$. And so in this case, $E$ is about $(p/N)^2\cdot N=p\cdot p/N$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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