Generalizing the *Ray-Chaudhuri--Wilson* theorem [8],
*Frankl* and *Wilson* [6] proved the following
intersection theorem, one of the most important results in extremal
set theory:

where , and for any two distinct :

Then

This theorem has numerous applications in combinatorics and in
geometry (e.g., the disproof of *Borsuk's conjecture* by *Kahn* and *Kalai* [7] (cf. [1], Sec. 5.6.), an
explicit construction of Ramsey graphs, and geometric applications
related to the Hadwiger-problem [6].)

*Frankl* and *Wilson* [6] asked whether inequality (1)
remains true when the modulus *p* is replaced by a composite number
*m*, or at least in the subcase *s*=*m*-1.

*Frankl* [5] answered the first of these questions
(arbitrary )
in the negative: he constructed faster growing
set-systems for *m*=6, as well as for *m*=*p*^{2}, *p* prime. For *m*=6,
*Frankl's* set-systems satisfy *s*=3 and
.

On the other hand, *Frankl* and *Wilson* [6] proved that
inequality (1) remains in force when *s*=*m*-1 and *m* is a prime power.

In this paper we consider non-prime-power moduli *m*. For any such
modulus, we give a very strong negative answer to both versions of the
Frankl-Wilson question: we prove that for *s*=*m*-1, no upper bound of
the form *n*^{f(m)} exists. More precisely, we prove the following.

- (a)
- ,
- (b)
- ,
- (c)
- .

We note that for fixed *m* (*m* is not a prime power), the size of
grows faster than any polynomial of *n*. This is quite
surprising, since previously it was believed that the failure of the
attempts to prove a polynomial upper bound was due to the lack of
techniques to handle non-prime-power composite moduli.

Our result gives a strong negative answer to a conjecture of *Babai* and *Frankl* ([1], Section 7.3, Conjecture C(r)).
*Babai* and *Frankl* conjectured that conditions (b) and (c)
of Theorem 1.2 imply

whereas our result shows that no bound of the form

We can even strengthen statement (c) of Theorem 1.2 as follows:

Let *m* be a positive integer, and suppose that *m* has *r*>1
different prime divisors:
.
Then there exists
*c*=*c*(*m*)>0, such that for every integer *h*>0,
there exists an explicitly constructible uniform set-system
over a
universe of *h* elements such that

- (a)
- ,
- (b)
- ,
- (c)
- the sizes of the pairwise intersections
(
,
)
occupy only 3 residue classes
mod
*m*, none of which is 0.

One of the striking applications of the Frankl-Wilson theorem for
prime moduli was an explicit construction of graphs of size
without homogeneous subsets (cliques or
anti-cliques) of size *n*. These are the largest explicit
Ramsey-graphs known to-date. As an application of our Theorem
1.2 , we give an alternative construction of explicit Ramsey
graphs of the same logarithmic order of magnitude, *i.e.,* of size
.
(But our *c*' is less than their *c*).

A key ingredient of our construction is a low-degree polynomial
constructed by *Barrington*, *Beigel* and *Rudich*
[2], to represent the Boolean ``OR'' function mod *m*. Any
reduction of the degree of such polynomials would yield improved
explicit Ramsey graphs.