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>, 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= |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?