Lower bounds are obtained on the degree and the number of monomials of
Boolean functions, considered as a polynomial over GF(2),
which decide if a given r-bit integer is square-free.
Similar lower bounds are also obtained for polynomials
over the reals which provide a threshold representation
more >>>