Disclaimer: these are my personal solutions; they have not been reviewed, so be careful relying on them as there might be errors. Some competitions may have official solutions from the contest publishers which you may wish to refer to instead if you’re looking for verified solutions.
Problem 8
Let $S$ be a finite set of polynomials in two variables, $x$ and $y$. For $n$ a positive integer, define $\Omega_n(S)$ to be the collection of all expressions $p_1 p_2 … p_k$, where $p_i \in S$ and $1 \le k \le n$. Let $d_n(S)$ indicate the maximum number of linearly independent polynomials in $\Omega_n(S)$. For example, $\Omega_2(\lbrace x^2, y \rbrace) = \lbrace x^2, y, x^2 y, x^4, y^2 \rbrace$ and $d_2(\lbrace x^2, y \rbrace) = 5$.
Find $d_2(\lbrace 1, x, x + 1, y \rbrace)$.
Find a closed formula in $n$ for $d_n(\lbrace 1, x, y \rbrace)$.
Calculate the least upper bound over all such sets of $\displaystyle{ \limsup_{n \to \infty} \frac{\log d_n(S)}{\log n} }$.
$\displaystyle{ \limsup_{n \to \infty} a_n = \lim_{n \to \infty}(\sup \lbrace a_n, a_{n + 1}, … \rbrace) }$, where $\sup$ means supremum or least upper bound.
Hints
Work in progress.
Solution to part (a)
Open to see the solution.
Let’s expand the set of such linearly-independent polynomials $\Omega_2(1, x, x+1, y)$ and then use that to compute the expression $d_2(\lbrace 1, x, x + 1, y \rbrace)$.
$$ \begin{align*} \Omega_2(1, x, x+1, y) & = \lbrace 1, x, x+1, y \rbrace & \quad \text{single terms} \\ & \quad \cup \lbrace 1^2, x^2, (x+1)^2, y^2 \rbrace & \quad \text{single terms repeated} \\ & \quad \cup \lbrace 1x, 1(x+1), 1y \rbrace & \quad \text{all pairs from $1$} \\ & \quad \cup \lbrace x(x+1), xy \rbrace & \quad \text{all pairs from $x$} \\ & \quad \cup \lbrace (x+1)y \rbrace & \quad \text{all pairs from $x+1$} \\ \end{align*} $$Afer expanding expressions and eliminating linearly-dependent terms, we are left with:
$$ \lbrace 1, x, x+1, y, x^2, x^2 + 2x + 1, y^2, x^2 + x, xy, xy + y \rbrace $$
which means that
$$ \boxed{ d_2(1, x, x+1, y) = 10 } \quad \blacksquare $$
Solution to part (b)
Still working on it.
Solution to part (c)
Still working on it.