1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

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