How many perfect squares exist?

Question

Consider a set of $1985$ positive integers not necessarily distinct. Every number in set can be written in the form $p_1^{{\alpha _1}}p_2^{{\alpha _2}} \cdots p_9^{{\alpha _9}}$ where $p_1,p_2,\ldots,p_9$ are distinct prime numbers and $\alpha_1,\alpha_2,\ldots,\alpha_9$ are non-negative integers. At least how many pairs of integers exist in this set such that their product is a perfect square?

Answer 1

Consider the map $f\colon n\mapsto(\alpha_1\bmod 2,\ldots,\alpha_9\bmod 2)\in\{0,1\}^{9}$. For two numbers $n,m$, the product $nm$ is a perfect square iff $f(n)=f(m)$. So if $c_1,\ldots,c_{512}$ are the cardinalities of preimages of the $1024$ elements of $\{0,1\}^{9}$, then we have $$\sum{c_i\choose 2}=\frac12\sum c_i^2-\frac12\sum c_i=\frac12\sum c_i^2-\frac{1985}2$$ such pairs. The quadratic sum becomes minimal (under the restriction of $\sum c_i=1985$) if the $c_i$ are "as equal as possible", so there must be $449$ times $c_i=4$ and $63$ times $c_i=3$, leading to a minimal (and actually achievable) result of $$449\cdot{4\choose 2}+63\cdot {3\choose 2}=2883.$$