Problem 1 (Barrington, Beigel and Rudich ) Does there exist a polynomial P in n variables, with integer coefficients, of degree , which weakly represents the n-variable OR function modulo 6? (Recall, that this means that , and for any .)
If the answer is yes for some
and the polynomials
are explicitly constructed, then our method yields explicit
For symmetric polynomials, Barrington, Beigel and Rudich  have shown that the degree is .
Showing only the existence of polynomials, weakly representing
the OR function with degree ,
would also have considerable
theoretical interest, since this result would imply the existence of
larger set-systems in Theorem 1.2. Here we should also mention
that the best lower bound is due to G. Tardos and Barrington . They proved that if the modulus m has r>1
different prime divisors, then every polynomial, weakly representing
the function ORn modulo m, has degree at least
Problem 2 Does there exist a quadratic polynomial P in n variables, with integer coefficients, which weakly represents the n-variable OR function modulo , where both and are ? If the answer is yes, then combining this P and the polynomial of Barrington, Beigel and Rudich , we would obtain a polynomial, satisfying the requirements of Problem 1.
Problem 3 It remains an open question whether, for a fixed positive integer m, a better than exponential ( upper bound holds for the size of set-systems satisfying that the size of each set is divisible by m while the sizes of their pairwise intersections are not divisible by m.
This problem is open even for m=6. Our main result shows that if m is not a prime power then no polynomial upper bound (O(nc)) holds. (If m is a prime power then a polynomial upper bound holds by Frankl - Wilson 1.1.)
Problem 4 If in Problem 3 we assume additionally that the sizes of the pairwise intersections occupy only two residue classes mod m then there may even be a polynomial upper bound (perhaps O(n2)), yet we are not aware of any better-than-exponential upper bound even for this case. This, too, is open for m=6.
Acknowledgments. The author wishes to thank Zoltán Király and David Mix Barrington for fruitful discussions and to Péter Frankl for valuable comments and suggestions. The author is especially grateful to Laci Babai for numerous helpful remarks and suggestions. The author acknowledges the support of grants OTKA T030059, FKFP 0607/1999, AKP 97-56 2,1.