TITLE: Convergence issues with infinite product of formal series
QUESTION [6 upvotes]: Question first:

Show that if $s_1 < s_2 < \dots$ is an increasing sequence of positive integers and $P(x)$ is a nonzero polynomial then we cannot have
  $$ P(x) \equiv \prod_{j=1}^\infty (1 - x^{s_j}) $$
  as formal series.

The right-hand side really means $\lim_{N \to \infty} \prod_{j=1}^N (1 - x^{s_j})$ where the notion of convergence is as described in this math.SE answer by Bill.
The intuition is that if we take $x \to 1^-$ then the left-hand side tends to zero at a slower rate than the right-hand side, since $P$ has the root $1$ with only finite multiplicity, while every factor on the RHS tends to zero. However, since formal and functional power series aren't actually the same thing (see link above), I'm not sure how to make this precise, even after formally inverting the $1-x$ factors on the left-hand side (by multiplying both sides by $(1+x+x^2+\dots+)^k$).
Does anyone know the correct incantations?
(For context, this came up in a solution to a recent IMO proposal. Since it was for high school students I swept the convergence issues under the rug, but myself I'd like to know exactly what the right thing to do is.)

REPLY [4 votes]: Equivalently, we'll show that we cannot have
$$\frac{1}{P(x)} = \frac{1}{\prod_{j=1}^{\infty} (1 - x^{s_j})}$$
as formal power series. The idea is that the LHS has a pole of finite order at $x = 1$ while the RHS has an essential singularity at $x = 1$. Precisely, the coefficients on the LHS have asymptotic growth a polynomial times an exponential. On the other hand, the coefficients of the RHS can be shown to have growth both strictly larger than any polynomial (by truncating the product) and strictly smaller than any exponential (by comparing to the growth rate in the case where $s_j = j$, which is known). So the two rates of growth can't match.


TITLE: How many different values for $5$ different numbers multiplying?
QUESTION [1 upvotes]: For example you have $2,3,4,5,6$ how many different numbers can you make by combining up to $5$ of them together in multiplication?
$2\times3\times4\times5$ is one number, $2\times3$ is another, $5$ is another, and so on....
What is the formula for this?

REPLY [1 votes]: Generically, we get $2^{|S|} - |S| - 1$ different piles of more than one number to multiply together.  Unfortunately, it's possible to get the same product many ways.  For instance, in the given example, $2\times6 = 3\times4$ and even better $2\times3 = 6$.  This is hard to deal with automatically; in fact, there's a somewhat similar problem called the subset sum problem that is known to be very computationally complex.  In this particular case, we get $32-5-1=26$ subsets, but only 21 distinct results: $12=2\times6=3\times4$, $24=2\times3\times4=4\times6$, $30=2\times3\times5=5\times6$, $60=2\times5\times6=3\times4\times5$, and $120=2\times3\times4\times5=4\times5\times6$ all appear twice.


TITLE: Density of "simultaneous squares"
QUESTION [2 upvotes]: Let $(u,v)$ be a pair of non-zero integers. We say that $(u,v)$ is a pair of simultaneous squares if for all primes $p$ dividing $u$, we have $\left(\frac{v}{p}\right) = 1$ and for all primes $q$ dividing $v$, we have $\left(\frac{u}{q} \right) = 1$. Here $\left(\frac{\cdot}{m}\right)$ denotes the Legendre symbol.
I want to estimate the number of pairs of simultaneous squares inside a box, say $0 < \max\{|u|, |v|\} \leq X$. Are there any asymptotic results known?

REPLY [5 votes]: This should be asymptotic to an expression of the form
$$\frac{cX^2}{\log X}$$
as $X \to \infty$, for some $c > 0$ (this should be interpreted as $(X/\sqrt{\log X}\,)^2$). Proving an upper bound of the correct order of magnitude in this case should not be too difficult using the large sieve (I can provide more details if you would like).
Proving the precise asymptotic formula is a bit more tricky. In the special case that $u$ and $v$ are odd, square-free, and coprime, this has been achieved in the paper
Friedlander, Iwaniec - Ternary quadratic forms with rational zeros
(see in particular section 2).
I expect that the methods from this paper could be adapted to handle your case.


TITLE: Prove $\sqrt{-7} \not\in \mathbb{Z}\left[\frac{2+3\sqrt{-7}}{4}\right]$
QUESTION [8 upvotes]: I have the following problem.

Consider the ring $\mathbb{Z}$ and define:
  $$x = \sqrt{-7}\qquad z = \frac{2+3x}{4}$$
  Show that $\mathbb{Z}[x] \not\subset \mathbb{Z}[z]$ and $\mathbb{Z}[z] \not\subset \mathbb{Z}[x]$.

First of all, I describe the ring extensions:
\begin{align}
\mathbb{Z}[x]
&= \left\{a_0 + a_1 x + a_2 x^2 +a_3 x^3 + \ldots  \ | \ a_i \in \mathbb{Z}\right\}\\
&= \left\{a + b x \ | \ a,b \in \mathbb{Z}\right\}
\end{align}
Where we use $x^2 + 7 = 0$ ($x$ is an algebraic integer). On the other hand
\begin{align}
\mathbb{Z}[z]
&= \left\{a_0 + a_1 z + a_2 z^2 +a_3 z^3 + \ldots  \ | \ a_i \in \mathbb{Z}\right\}
\end{align}
admits no further simplification (we have $16z^2 - 16z + 67 = 0 \Rightarrow z$ is not an algebraic integer).

I think it is easy to show $z \not\in \mathbb{Z}[x]$. To see this, assume you can find $a,b\in \mathbb{Z}$ such that $z = a+bx$. Now consider this identity in $\mathbb{Q}(x) = \mathbb{Q}[x]$, where $\{1,x\}$ is a basis. Since
$$z=\frac{2}{4} + \frac{3}{4}\!x= a +bx $$
it must be $a=\frac{2}{4}$, $b=\frac{3}{4}$, so $a, b$ are not in $\mathbb{Z}$. Thus $z\not\in\mathbb{Z}[x]$.

Is this correct?
Any idea for the other part?

REPLY [1 votes]: Your proof for $z\not\in\mathbb{Z}[x]$ is correct.  For $x\not\in\mathbb{Z}[z]$, a nice trick is to consider what's going on mod 3.  Note that $\mathbb{Z}[z]\cong\mathbb{Z}[t]/(16t^2-16t+67)$ and $2$ is a root of $16t^2-16t+67$ mod $3$, so there is a homomorphism $\varphi:\mathbb{Z}[z]\to \mathbb{F}_3$ such that $\varphi(z)=2$.  (Intuitively, this is just a rigorous version of saying that mod $3$, $z=\frac{2+3\sqrt{-7}}{4}=\frac{2}{4}=2$.)
Now suppose $x$ were in $\mathbb{Z}[z]$.  Then $\varphi(x)$ would satisfy $\varphi(x)^2=-7=2$ in $\mathbb{F}_3$.  Since $2$ is not a square in $\mathbb{F}_3$, this is a contradiction.