Let
*P*(*z*_{1},*z*_{2},...,*z*_{n}) be a polynomial of degree *d*
which satisfies that
,
and for every

An explicit construction of such

Using the polynomial

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

Lemma 3.1 easily yields Theorem 1.2 setting
and using elementary estimations for the binomial
coefficients.

**Proof of Lemma 3.1**. *Q* can be written as

where , and is integer, . Let us define

where is the smallest, positive integer, congruent to modulo

Let the function
be defined as

Let

We note that . Conversely, if then

By equation (4), the polynomial
is a sum of the monomials
of the form
.
We wish to keep all coeffcients equal to 1; therefore we shall
say that the monomial
occurs with *multiplicity*
in this sum. Note that each multiplicity is a nonnegative
integer .
Consequently, the matrix *A* is a sum of the matrices
,
corresponding to the monomial
in the following way:

This matrix occurs in the sum with multiplicity . It is easy to verify that is permutationally equivalent to the matrix

where the diagonal blocks

- (a)
- every cell of the main diagonal of
*A*is covered by the same number of*B*-blocks, and this number is divisible by*m*; - (b)
- for any pair of cells of the main diagonal of
*A*, the number of those*B*-blocks which cover both members of the pair, is not divisible by*m*.

For part (b), we note that the

assuming, as we may, that .

We note that the number of edges containing each vertex is

Now we are ready to complete the proof of Lemma 3.1.
Let us consider the dual of the hypergraph of Corollary 3.3, i.e.,
let the universe be the set of *B*-blocks, and if a *B*-block was present
*a* times in the hypergraph ,
then it will correspond to *a*
different points (or elements) in the universe. Consequently, our
universe is a set (rather than a multiset). The size of the
universe is
*h* < 2(*m*-1)*n*^{2d}/*d*!.
The diagonal cells of *A* correspond to the
members of the set-system :
the set corresponding
to cell (*x*,*x*) consists of exactly those *B*-blocks which cover (*x*,*x*).
Therefore
Since every diagonal cell of *A* is covered by the same number of
*B*-blocks, the resulting
is a uniform set system.
As discussed previously, this number (the size of the members of
)
is
.
From Corollary 3.3, statements (a), (b), (c) of Lemma 3.1
follow.

To prove the estimate on the size of the members of
in terms of *h* (the number of vertices of )
given in Remark 1.3, we first add dummy vertices to increase *h*
to its upper bound
stated above.
Now, since this quantity is still
,
we see,
using the bound *d*=*O*(*n*^{1/r}) guaranteed by Theorem 2.2, that

and therefore the size of the members of is

as claimed in equation (2).

**Proof of Theorem 1.4**. The statement is immediate
if the polynomial *P*' of Corollary 2.4 is used for the
construction of the set-system
in the proof of Theorem 1.2
in the place of the polynomial *P*.

**Proof of Corollary 1.6** Let
,
and apply Theorem 1.4 for
constructing a set-system
for *h* and this *m*'. The
intersections occupy only 3 residue classes modulo *m*'. Now replace
every point of the universe by *m*/m' new points; the new points will
be the members of exactly the same sets of the set-system as the old
point. The statement follows.