MathDB

8

Part of 1979 VTRMC

Problems(1)

1979 VTRMC #8

Source:

8/8/2018
Let SS be a finite set of polynomials in two variables, xx and yy. For nn a positive integer, define Ωn(S) \Omega _ { n } ( S ) to be the collection of all expressions p1p2…pk, p _ { 1 } p _ { 2 } \dots p _ { k } , where pi∈Sp_i \in S and 1≤k≤n1\leq k \leq n. Let dn(S)d_n(S) indicate the maximum number of linearly independent polynomials in Ωn(S) \Omega _ { n } ( S ) . For example, Ω2({x2,y})={x2,y,x2y,x4,y2} \Omega _ { 2 } \left( \left\{ x ^ { 2 } , y \right\} \right) = \left\{ x ^ { 2 } , y , x ^ { 2 } y , x ^ { 4 } , y ^ { 2 } \right\} and d2({x2,y})=5d _ { 2 } \left( \left\{ x ^ { 2 } , y \right\} \right) = 5
(a) Find d2({1,x,x+1,y}) d _ { 2 } ( \{ 1 , x , x + 1 , y \} ) . (b) Find a closed formula in nn for dn({1,x,y}) d _ { n } ( \{ 1 , x , y \} ) . (c) Calculate the least upper bound over all such sets of lim‾n→∞log⁡dn(S)log⁡n \overline{\text{lim}} _ { n \rightarrow \infty } \frac { \log d _ { n } ( S ) } { \log n } (lim‾n→∞an=lim⁡n→∞(sup⁡{an,an+1,…} \overline{\text{lim}} _ { n \rightarrow \infty } a _ { n } = \lim _ { n \rightarrow \infty } ( \sup \left\{ a _ { n } , a _ { n + 1 } , \ldots \right\} , where sup means supremum or least upper bound.)