.PH ""
.EQ
delim $$
define eqsl % "\o'\(==\(sl'" %
tdefine dim % roman "dim" %
ndefine FF % F under %
ndefine cc % c under %
tdefine cc % bold c %
tdefine FF % bold F %
define mod % roman "mod" %
.EN
.de ST
.sp
.ta 6iR
	\(sq
.sp
..
.nr Pt 1
.am DE
.sp
.ls 2
..
.ce 99
.B
On Subsets with Cardinalities of
Intersections Divisible by a Fixed Integer
.R
.sp
by
.sp
.I
P. Frankl
.R
.sp
Bell Laboratories
Murray Hill, New Jersey 07974
USA
.sp
and
.sp
CNRS
Paris, France
.sp
and
.sp
.I
A. M. Odlyzko
.R
.sp
Bell Laboratories
Murray Hill, New Jersey 07974
USA
.sp 3
.I
Abstract
.R
.sp 2
.ce 0
.P
If $m(n,l)$ denotes the maximum number of
subsets of an $n$-element set such that the
intersection of any two of them has cardinality
divisible by $l$, then a trivial construction shows that
.DS 2
.EQ
m(n,l)~>=~2 sup [n/l]~.
.EN
.DE
.ls 1
.sp
For $l~=~2$, this was known to be essentially best possible.
For $l~>=~3$, we show by construction that
$m(n,l)2 sup -[n/l]$ grows exponentially in $n$,
and we provide upper bounds.
.bp
.ce 99
.B
On Subsets with Cardinalities of
Intersections Divisible by a Fixed Integer
.R
.sp
by
.sp
.I
P. Frankl
.R
.sp
Bell Laboratories
Murray Hill, New Jersey 07974
USA
.sp
and
.sp
CNRS
Paris, France
.sp
and
.sp
.I
A. M. Odlyzko
.R
.sp
Bell Laboratories
Murray Hill, New Jersey 07974
USA
.sp 3
.ce 0
.ls 2
.H 1 Introduction
We consider the problem of estimating $m(n,l)$ which
.PH "''- \\\\nP -''"
.pn 2
is the maximum number of subsets $A sub 1 , "..." ,A sub m$
of an $n$-element set such that
.DS 2
.EQ
| A sub i ^\(ca^ A sub j |~==~0~~( mod ~l),~~~
1~<=~i~<~j~<=~m~.
.EN
.DE
Suppose $B sub 1 , "..." ,B sub [n/l]$ are pairwise disjoint
$l$-element subsets of $"{" 1,2, "..." ,n "}"$.
Then the sets formed by the union of any collection of
the $B sub i$ has the desired property, and so
.DS 2
.EQ (1.1)
m(n,l)~>=~2 sup [n/l]~.
.EN
.DE
P. Erdo\*:s conjectured that this is essentially best possible
for $l~=~2$.
This was proved by Berlekamp [1] and Graver [5] by different
methods.
They showed that if $n~=~8$ or $n~>=~10$, then
.DS 3
.EQ
m(n,2)~mark =~2 sup n/2~~~if~~n~roman {is~even}~,
.EN
.sp
.EQ
m(n,2)~lineup =~2 sup (n-1)/2 ^+^1 ~~~if~n~roman {is~odd}~.
.EN
.DE
It turns out that for $l~>~2$, the natural generalization,
namely that
.DS 2
.EQ (1.2)
m(n,l)~=~O(2 sup n/l )~,
.EN
.DE
is false.
We prove the following bounds for $m(n,l)$.
.sp
.I
Theorem 1.
If a Hadamard matrix of order $4l$ exists (which is known
to be true for $1~<=~l~<=~66$, and is conjectured to be
true for all $l$), then
.DS 2
.EQ (1.3)
m(n,l)~>=~(8l) sup [n/(4l)]~.
.EN
.DE
In any event, for $l~>=~67$
.DS 2
.EQ (1.4)
m(n,l)~>=~256 sup [n/(4l)]~=~2 sup 8[n/(4l)]~.
.EN
.DE
Theorem 2.
If $OMEGA (l)$ is the number of prime-power divisors of $l$, then
.DS 2
.EQ (1.5)
m(n,l)~<=~2 sup [n/2]~+~OMEGA (l)n~,
.EN
.DE
and
.DS 2
.EQ (1.6)
m(n,l)~<=~2~ sum from i=0 to {[ n/(2l) ]} ~
left ( pile {n above i } right )~+~OMEGA (l)n~.
.EN
.DE
.R
.P
For $l~=~2,3,4$ the bound (1.5) is better than (1.6),
but for larger values of $l$, (1.6) is sharper, and it
is markedly so for large $l$.
It is not hard to show that
.DS 2
.EQ
c(l)~=~lim from {n -> inf}~m(n,l) sup 1/n
.EN
.DE
exists, and the two theorems imply that
.DS 2
.EQ (1.7)
c(l)~>=~exp ( 1 over 4l^log^8l )
.EN
.DE
if a Hadamard matrix of order $4l$ exists, and that
.DS 2
.EQ (1.8)
c(l)~<=~min ( sqrt 2 ,~exp (h((2l) sup -1 ) ))~,
.EN
.DE
where $h(x)~=~-x^log^x~-~
(1-x)^log^(1-x)$ is the entropy function
(with $log^(x)~=~log sub e (x))$.
For $l~->~inf$, (1.7) gives
.DS 2
.EQ
c(l)~>=~1~+~1+o(1) over 4l^log^l~,
.EN
.DE
while (1.8) yields
.DS 2
.EQ
c(l)~<=~1~+~1+o(1) over 2l^log^l~.
.EN
.DE
.P
It would be very interesting to know whether one
has equality in (1.7).
Some other open questions are discussed in Section 4.
.H 1 Constructions
Let $m sub 1 (n,l)$ denote the maximum size of a collection
of subsets
$A sub 1 , "..." , A sub m$ of $"{" 1, "..." ,m "}"$ such that
.DS 2
.EQ
| A sub i ^\(ca^ A sub j |~==~0~~
( mod~l),~~~1~<=~i,j~<=~m~,
.EN
.DE
(i.e. we omit the condition $i~!=~j$).
.sp
.I
Lemma 1.
We have
.DS 2
.EQ
m sub 1 (n,l)~<=~m(n,l)~<=~m sub 1 (n,l)~+~
OMEGA (l)n~,
.EN
.DE
where $OMEGA (l)$ denotes the total number
of prime factors of $l$, multiple factors
counted according to their multiplicity.
.sp
Proof.
.R
The first inequality of the lemma is trivial.
To
prove the second suppose that $| A sub i |~eqsl~0~~( mod~l)$ for $1~<=~i~<=~k~<=~m$ and let $B~=~(b sub ij )$ be
the incidence matrix of the collection
$A sub 1 , "..." ,A sub k$; i.e.,
.DS 2
.EQ
b sub ij ~=~left {
matrix {
ccol {1 above nothing above 0}
ccol {nothing above nothing above nothing}
ccol {if above nothing above if}
lcol {i~member~A sub j~, above nothing above
i~nomem~A sub j~,}
}
.EN
.DE
where
$| A sub i ^\(ca^ A sub i |~==~0$
(mod $l$) for $1~<=~i~<~j~<=~k$.
To prove the lemma, it is sufficient to prove
$k~<=~OMEGA (l)n$.
$B$ has $n$ rows, so rank $(B)~<=~n$.
Next set
.DS 2
.EQ
C~=~B sup T B~.
.EN
.DE
If $C~=~(c sub ij )$, then
.DS 2
.EQ
c sub ij~=~| A sub i ^\(ca^ A sub j |~.
.EN
.DE
Let $l~=~prod from i=1 to r~p sub i sup alpha sub i$,
where the $p sub i$ are distinct primes.
As $| A sub j |~eqsl~0$ (mod $l$),
$| A sub j |~eqsl~0$ (mod $p sub i sup alpha sub i )$ for
some $i,1~<=~i~<=~r$.
.P
For a fixed $i,1~<=~i~<=~r$, and for a fixed
$beta ,~ 1~<=~beta~<=~alpha$, let
$A sub i sub 1 , "..." , A sub i sub s$ be the sets for which
.DS 3
.EQ
| A sub i sub j | ~mark ==~0~~~( mod~p sub i sup {beta -1} )~,
.EN
.sp
.EQ
| A sub i sub j | ~lineup eqsl ~0~~~
( mod~p sub i sup beta )~.
.EN
.DE
The submatrix of $C$ formed by taking rows and columns
numbered $i sub 1 , "..." ,i sub s$ becomes, when divided
by $p sub i sup {beta -1}$, a diagonal matrix mod $p sub i$
with non-zero entries on the diagonal.
This implies $s~<=~n$, since
$roman rank ~C~=~roman rank~B~<=~n$.
Summing over $i$ and $beta$, we obtain the claim of the lemma.
.ST
.I
Lemma 2.
For $1~<=~r~<=~n$,
.DS 2
.EQ
m sub 1 (n,l)~>=~m sub 1 (r,l)m sub 1 (n-r,l)~.
.EN
.DE
Proof.
.R
Suppose $A sub 1 , "..." , A sub s$ are subsets
of $"{" 1,2, "..." ,r "}"$ such that
.DS 2
.EQ
| A sub i ^\(ca^ A sub j |~==~0~~( mod~l),~~~
1~<=~i,j~<=~s~,
.EN
.DE
and $B sub 1 , "..." ,B sub t$
are subsets of $"{" r+1 , "..." ,n "}"$ such that
.DS 2
.EQ
| B sub i ^\(ca ^B sub j |~==~0~~( mod ~l)~,~~~
1~<=~i,j~<=~t~.
.EN
.DE
Define
.DS 2
.EQ
C sub i,j ~=~A sub i ^\(cu^B sub j~,~~~
1~<=~i~<=~s,~~1~<=~j~<=~t~.
.EN
.DE
Then the $C sub i,j$ are all distinct, and
.DS 2
.EQ
| C sub i,j ^ \(ca^C sub p,q |~=~
| A sub i ^\(ca^A sub p |~+~
| B sub j ^\(ca^B sub q |~==~0~~~( mod~l)~,
.EN
.DE
which proves the lemma.
.ST
.P
We now proceed to our constructions of large collections
of subsets $A sub 1 , "..." ,A sub m$ of
$"{" 1, "..." ,n "}"$ such that
.DS 2
.EQ
| A sub i ^\(ca^A sub j |~==~0~~~
( mod~l)~,~~~1~<=~i,j~<=~m~.
.EN
.DE
These constructions are based on Hadamard matrices.
Recall that a Hadamard matrix $M$ of order $4t$ is a
$4t$ by $4t$ matrix with $+- 1$ entries such that the
scalar product of any two distinct rows is zero.
One can always assume that the first row is of the
form $(1, 1, "..." ,1)$.
.P
It is conjectured that Hadamard matrices of order $4t$
exist for every $t~member~Z sup +$ and this is known to
be true for $t~<=~66$, as well as for several infinite
families of values of $t$, including $t~==~3$ (mod 4),
$t$ a prime power \(em cf. [4].
.P
Assume first that a Hadamard matrix $M~=~(m sub ij )$
of order $4l$ exists.
Define subsets
$S sub 1 , "..." , S sub 4l ,~T sub 1 , "..." , T sub 4l$
of $"{" 1 , "..." , 4l "}"$ by
.DS 3
.EQ
S sub i~mark =~
"{" j~:~1~<=~j~<=~4l,~m sub ij ~=~1 "}"
.EN
.sp
.EQ
T sub i~lineup =~
"{" j~:~ 1~<=~j~<=~4l ,~m sub ij~=~-1 "}"~.
.EN
.DE
Of course $T sub i~=~"{" 1, "..." ,4l "}"~-~S sub i$,
$T sub 1~=~empty$.
The orthogonality of the rows implies
.DS
.TS
l l l.
a)	$| T sub i |~=~| S sub i |~=~2l$,	$2~<=~i~<=~4l$,
.sp
b)	$| S sub i^\(ca^S sub j |~=~| T sub i ~\(ca~T sub j |~=~l$,	$2~<=~i~<~j~<=~4l$,
.sp
c)	$| T sub i ^\(ca^S sub j |~=~l$,	$2~<=~i,j~<=~4l,~~i~!=~j$.
.TE
.DE
.P
Setting
$FF~=~"{" T sub 1 , T sub 2 , "..." , T sub 4l ,~S sub 1 , "..." , S sub 4l "}"$,
we deduce that $| F ^\(ca^F prime |~==~0$ (mod $l$) holds for
$F,F prime~member~FF$.
Thus
.DS 2
.EQ
m sub 1 (4l,l)~>=~8l~,
.EN
.DE
and so, by Lemmas 1 and 2
.sp -.5
.DS 2
.EQ
m(n,l)~>=~m sub 1 (n,l)~>=~(8l) sup [n/(4l)]~.
.EN
.DE
.sp -.5
.P
Now consider the hypothetical case that there is no Hadamard
matrix of order $4l$.
Suppose $l~=~l sub 1 + "..." + l sub q$, where
$l sub 1~<=~l sub 2~<=~"..."~<=~l sub q$, and
$l sub i~member~Z sup +$ are such that Hadamard
matrices $M sub i$ of order $4l sub i$ exist.
.sp -.5
.P
Let $S sub j (i)$, $T sub j (i)$,
$1~<=~j~<=~4l sub i$,
$1~<=~i~<=~q$ be the sets obtained from the matrices
$M sub i$ by our construction above, where we can assume
that $S sub j (i)$ and $T sub j (i)$ are subsets of
$"{" 4l sub 1 + "..." + 4l sub i-1 + 1 , "..." , 4l sub 1 + "..." + 4l sub i "}"$.
Now define, for $1~<=~j~<=~4l sub 1$,
.DS 3
.EQ
S sub j~mark =~union from i=1 to q~S sub j (i)~,
.EN
.sp
.EQ
T sub j~lineup =~
union from i=1 to q~T sub j (i)~.
.EN
.DE
It is straightforward to verify that these sets have
pairwise intersections of cardinality divisible by $l$,
and so
.sp -.5
.DS 2
.EQ
m sub 1 (4l,l)~>=~8l sub 1~.
.EN
.DE
Since every integer $l~>=~67$ can be written
as the sum of integers from $"{" 33, 34, "..." ,66 "}"$,
an application of Lemmas 1 and 2 yields the desired lower bound.
.sp -.5
.P
The bound (1.4) can be improved for large $n$ and $l$
even without assuming unproved hypotheses about existence
of Hadamard matrices.
It can be shown that $l$ has a representation $l~=~l sub 1 + "..." + l sub q$
with $l sub i~>=~epsilon l$, $epsilon~>~0$ a fixed constant,
such that Hadamard matrices of order $4l sub i$ exist,
which enables one to replace 256 by $8 epsilon l$.
.sp -.5
.ST
.sp -.5
.H 1 "Upper bounds"
.sp -.5
First we derive the upper bound
.DS 2
.EQ (3.1)
m sub 1 (n,l)~<=~2 sup [n/2]~.
.EN
.DE
Suppose $A sub 1 , "..." ,A sub m$ are subsets of $"{" 1 , "..." ,n "}"$
such that
.DS 2
.EQ
| A sub i ^\(ca^ A sub j |~==~0~~( mod~l),~~~
1~<=~i,j~<=~m~.
.EN
.DE
Let $cc sub i$ be a vector
of length $n$ defined by
.DS 2
.EQ
( cc sub i ) sub j~=~left {
matrix {
ccol {1 above 0}
ccol {nothing above nothing}
ccol {if above if}
lcol {j~member~A sub i~, above j ~nomem~A sub i~.}
}
.EN
.DE
Let $p$ be a prime divisor of $l$.
Consider the vector space $C$ over $GF(p)$ spanned
by the $cc sub i$.
Then $C$ is self-orthogonal, since
.DS 2
.EQ
cc sub i cdot cc sub j~=~0~,~~~
1~<=~i,j~<=~m~.
.EN
.DE
Therefore, by basic linear algebra ([6]),
.DS 2
.EQ
dim~C~<=~[n/2]~.
.EN
.DE
Now each $cc sub i$ is a $0-1$ vector in $C$,
thus (3.1) follows from the following result.
.sp
.I
Theorem 3
.R
([7]).
.I
Suppose that $U$ is a $k$-dimensional subspace
of a vector space $V$ over some field.
Then, in any coordinate system for $V$, $U$
has at most $2 sup k$ $0-1$ vectors.
.R
.P
Combining (3.1) and Lemma 1 we obtain (1.5).
.P
In order to prove (1.6) we need the following
result (a somewhat weaker bound follows from results in [8]).
.sp
.I
Theorem 4
.R
([3; Theorem 11]).
.I
Suppose $FF$ is a collection of subsets of $"{" 1,2, "..." ,n "}"$
such that for $F~!=~F prime$, $F, F prime~member~FF$,
$| F ^\(ca^ F prime |$ takes only $s$ values.
Then
.R
.DS 2
.EQ
| FF |~<=~sum from i=0 to s~left ( pile {n above i} right )~.
.EN
.DE
.P
In view of Lemma 1 it is sufficient to prove
.DS 2
.EQ (3.2)
m sub 1 ( n,l)~<=~2~sum from i=0 to [n/(2l)]~
left ( pile {n above i} right )~.
.EN
.DE
Suppose without loss of generality that $A sub 1 , "..." ,A sub k$
have cardinalities $<=~n/2$, and $A sub k+1 , "..." ,A sub m$
have cardinalities $>~n/2$.
.P
Then $| A sub i ^\(ca^ A sub j |~member~"{" 0, l , "..." , [n/(2l)]l "}"$,
$1~<=~i,j~<=~k$, and moreover
$| A sub i ^\(ca^A sub j |~=~[n/(2l)]l$ implies $i~=~j$.
Thus, by Theorem 4, we have
.DS 2
.EQ (3.3)
k~<=~sum from i=0 to [n/(2l)]~left ( pile {n above i} right )
.EN
.DE
Next, define
$B sub i~=~"{" 1,2, "..." ,n "}"~-~A sub i~,~~~k+1~<=~i~<=~n$.
Then
$| B sub i ^\(ca^B sub j |~=~n~-~| A sub i |~-~| A sub j |~+~| A sub i ^\(ca ^A sub j |~==~n~~~( mod~l)$, moreover
for $i~!=~j$ we deduce
$| B sub i ^\(ca^B sub j |~<=~n/2-l~=~(n-2l)/2$.
Thus $| B sub i^\(ca^B sub j |$ for
$i~!=~j$ takes at most $[n/(2l)]$ different values.
Again from Theorem 4 we obtain
.DS 2
.EQ (3.4)
m-k~<=~sum from i=0 to [n/(2l)]~left ( pile {n above i} right )~.
.EN
.DE
From (3.3) and (3.4) the bound (3.2) and thus (1.6) follows.
.ST
.H 1 "Related problems."
Our paper leaves a number of questions open.
The main problem, as stated in the introduction,
is to determine $c(l)$.
Barring that, it would be interesting to decide
whether $c(l)$ is monotone decreasing.
(At this point we only know that $c(2)~>=~c(l)$
for $l~=~3,4$, and $c(2)~>~c(l)$ for $l~>=~5$.)
.P
One can also ask similar questions about collections
of equal-sized sets.
Let $k$ be a positive integer and $I$ a subset of
$"{" 0, 1 , "..." ,k-1 "}"$.
Denote by $m(n,k,I)$ the maximum number of $k$-subsets
of an $n$-set such that the intersection of any two
distinct sets has cardinality belonging to $I$.
It was proved in [2] that
for $n~>~n sub 0 (k,I)$,
.DS 2
.EQ (4.1)
m(n,k,I)~<=~prod from {i member I}~
(n-i)/(k-i)~.
.EN
.DE
In particular, if $n~=~bl$,
$k~=~al$, and $I~=~"{" 0,l, "..." ,(a-1)l "}"$,
then (4.1) gives
.DS 2
.EQ (4.2)
m(n,k,I)~=~left ( pile {b above a} right )~.
.EN
.DE
.P
It would be nice to know given $a$ and $l$ what
is the least value of $b sub 0$ such that for
$b~>=~b sub 0$ and $n~=~bl$, $k~=~al$, (4.2)
holds.
Binary self-dual codes show that in general
the bound $left ( pile {b above a} right )$ does not
hold even for $l~=~2$.
.P
One can generalize our problem by asking for $m(n,l,s)$,
the maximum number of subsets of an $n$-set, such that
the intersection of any $s$ distinct ones has cardinality
divisible by $l$.
.P
Obviously $m(n,l,s)~>=~2 sup [n/l]$.
It can be shown that
.DS 2
.EQ
c(l,s)~=~lim from {n -> inf}~m(n,l,s) sup 1/n
.EN
.DE
exists, and that $c(l,s)$ is monotone nonincreasing in $s$.
It seems reasonable to conjecture that for $s~>~s(l)$, $c(l,s)~=~2 sup 1/l$.
.bp
.ce
.B
REFERENCES
.R
.sp
.RL
.LI
E. R. Berlekamp, On subsets with intersections of even cardinality.
Canad. Math. Bull. \f212\f1(1969), 363-366.
.LI
M. Deza, P. Erdo\*:s, P. Frankl,
Intersection properties of systems of finite sets.
Proc. London Math. Soc. \f236\f1(1978), 369-384.
.LI
P. Frankl, R. M. Wilson, Intersection theorems with geometric
consequences.
Combinatorica \f21\f1(1981), 357-368.
.LI
A. V. Geramita, J. Seberry, \f2Orthogonal designs\f1.
Lecture notes in pure and applied mathematics, Vol. 45,
Marcel Dekker,
New York 1979.
.LI
J. E. Graver, Boolean designs and self-dual matroids,
Lin. Alg. Appl. \f210\f1 (1975), 111-128.
.LI
F. J. MacWilliams, N. J. A. Sloane,
\f2The theory of error-correcting codes\f1,
North Holland 1978.
.LI
A. M. Odlyzko, On the ranks of some (0,1)-matrices
with constant row sums.
J. Austral. Math. Soc. \f231\f1(1981), 193-201.
.LI
D. K. Ray-Chaudhuri, R. M. Wilson, On $t$-designs.
Osaka J. Math. \f212\f1(1975), 735-744.
.LE