Table of LCM's vs. table of products I think there'll be about as many numbers of the form lcm$(a,b)$. Ford counts integers having a divisor in an interval $[y,2y]$, and one should be able to adapt this to counting square-free integers with such a divisor. Of course, a square-free integer in the multiplication table arises also as lcm$(a,b)$.

Polynomials vanishing modulo some integer $n$ A bit unclear to me what you are looking for. Suppose $p$ and $q$ are primes with say $q$ of size about $p^2$. Then $(t^p-t)q$ is a polynomial that is zero mod $n=pq$, and the coefficients are of size at most $q=o(n)$, and the degree is $p = o(p+q)$. Does that qualify as a counterexample?