From daw@joseph.cs.berkeley.edu Mon Apr  7 00:12:09 PDT 1997
Article: 64991 of sci.crypt
Path: agate!not-for-mail
From: daw@joseph.cs.berkeley.edu (David Wagner)
Newsgroups: sci.crypt
Subject: Re: Combinatorial problem
Date: 6 Apr 1997 23:57:28 -0700
Organization: ISAAC Group, UC Berkeley
Lines: 70
Message-ID: <5ia5so$2aa@joseph.cs.berkeley.edu>
References: <5hv4sd$rst$1@scream.auckland.ac.nz> <860132735.29145@dejanews.com>
NNTP-Posting-Host: joseph.cs.berkeley.edu
Bcc: daw@cs.berkeley.edu

In article <860132735.29145@dejanews.com>,  <bob_jenkins@compuserve.com> wrote:
> In article <5hv4sd$rst$1@scream.auckland.ac.nz>,
>   daw@cs.berkeley.edu (David Wagner) wrote:
> > Given a group (G,+) and a subset S of G.  You are to find subsets T,U of
> > G with the property
> > (*)     for all s in S, there exists t in T and u in U such that s = t + u.
> > You are to make |T| + |U| as small as conveniently possible.
> 
> You can always have T={0}, U=S, so |T|+|U| = |S|+1.
> 
> If you had a,b in T and c,d in U so that
>   a+c in S
>   a+d in S
>   b+c in S
>   b+d in S
> then (a+c)-(b+c) = (a+d)-(b+d).
> You could look at this as 4 linearly dependent equations with 3
>   unknowns; the dependence is what produced the last equality.
> More generally, |U|+|T| is a set of |U|*|T| linearly dependent
>   equations with only |U|+|T|-1 unknowns.
> 
> For small |S|, that is |S| < |G|^^(1/4),
> there are less than sqrt(|G|) values of (x-y) where x,y in S,
> so by the birthday paradox there won't be any collisions like
>   (x-y)=(w-z) where x,y,w,z in S,
> so you can't do any better than |T|+|U|=|S|+1.
> 
> That leaves the range |G|^^(1/4) < |S| < 2sqrt(|G|)
>   unaccounted for.  Anyone inspired to handle that range?

Thank you for the excellent analysis!
Yes, I can extend your techniques to handle that range, and surprisingly
the trivial solution T={0},U=S is very close to the optimum.

You showed that (if S = T+U) we must we have at least one equation of the
form w=x-y+z with x,y,w,z in S. In fact, I claim that we get many more: at
least |S| (|S| - (|T|+|U|) + 1)/4, to be precise.

[ Proof: pick a,A in T, b,B in U, and note that we can write
        a+b = (a+B) - (A+B) + (A+b).
  All these equations are different, so long as we require a<A, b<B.
  Therefore we get C(|T|,2) C(|U|,2) different equations, where C(i,2)
  represents the binomial coefficient "i choose 2"; this can be rewritten
  as |T| (|T|-1) |U| (|U|-1) / 4 = |S| (|S| - (|T|+|U|) + 1)/4. ]

Now note that by the birthday paradox, we get about |S|^4 / (24 |G|)
collisions of the form w=x-y+z with w,x,y,z in S (for average S); and
if we can write S = T+U, we will need at least |S| (|S| - (|T|+|U|) + 1)/4
such collisions, so we obtain the inequality
	|S|^4 / (24 |G|) >= |S| (|S| - (|T|+|U|) + 1)/4.
Clearing denominators and dividing by |S|, we get
	|S|^3 >= 6 |G| (|S| - (|T|+|U|) + 1) >= 6 |G| |S|  - 6 |G| (|T|+|U|).
Solving for |T|+|U|, we obtain the bound
	|T|+|U| >= |S| - |S|^3 / (6 |G|).

For instance, if |S| <= 2 sqrt(|G|), we see |T|+|U| >= |S|/3; so using
T={0},U=S can only be (at most!) a factor of 3 worse than optimal.
On the other hand, we already know |T|+|U| = 2 sqrt(|G|) is attainable
[ by the birthday paradox: pick T,U randomly with |T|=|U|=sqrt(|G|) ]
so when |S| >= 2 sqrt(|G|) we can get |T|+|U| <= |S|.

This still leaves a bit of a possible gap: when |S| >> sqrt(|G|), the
bound obtained by your (generalized) techniques is useless.  Trivially
        sqrt(|S|) <= |T|+|U| <= |S|.
We've seen that when |S| <= 2 sqrt(|G| we can sharpen this to
|S|/3 <= |T|+|U| <= |S| for the optimal T,U, and the lower end of the
inequality is easily attainable.  However, for |S| >> sqrt(|G|), we
know that sqrt(|S|) <= |T|+|U| <= 2 sqrt(|G|) << |S| for optimal T,U,
but this still leaves a gap for sqrt(|G|) << |S| << |G|.  Perhaps this
gap can be narrowed too?