Subset sum "cubes" and the complexity of primality testing

A E-3(2) Boolean circuit has 3 levels of gates. The input level is comprised of OR gates each taking as inputs 2, not necessarily distinct, literals. Each of these ORs feeds one or more AND gates at the second level. Their outputs form the inputs to a single OR gate at the output level. Using the projection technique of Paturi, Saks, and Zane, it is shown that the smallest Z(3)(2) Boolean circuit testing primality for any number given by n binary digits has size 2(n-g(n)) where g(n) = o(n). Disjunctive normal form (DNF) formulas can be considered to be a special case of Sigma(3)(2) circuits, and a bound of this sort applies to them too. The argument uses the following number theoretic fact which is established via a modified version of Gallagher's "Larger" Sieve: Let a(1) < a(2) < ... < a(Z) be distinct integers in {1,...,N}. If a(0) + epsilon(1)a(1) + epsilon(2)a(2) + ... + E(Z)a(Z) is prime for all choices of epsilon(1), epsilon(2), ..., epsilon(Z) is an element of {0, 1}, then Z less than or equal to (9/2 + o(1)) logN/log logN. (C) 2004 Published by Elsevier B.V.