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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .