Mixing
If $fin mathbbZ[x]$ is a polynomial and $f(2^n)$ is a perfect square for all $n$, then there is a $gin mathbbZ[x]$ such that $f=g^2$
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
If $fin mathbbZ[x]$ is a polynomial and $f(2^n)$ is a perfect square for all $n$, then there is a $gin mathbbZ[x]$ such that $f=g^2$
I understand that there might be an issue with the problem statement but I don't know anything further.
Here's a link that might help (related problem).
EDIT : I see the exact problem posted in AoPS long time ago. I couldn't understand the solution posted there.
I'm quoting user Math154's solution :
Multiplying by the square of $f$'s denominator if necessary, WLOG $finmathbbZ[x]$ and $t_n=sqrtf(2^n)inmathbbZ^+$ for all $nge1$.
First suppose that $d=deg f$ is even, so $f(x)=cg(x)^2+h(x)$ for polynomials $g,hinmathbbQ[x]$ with $degg=d/2$ and $degh<d/2$ and a positive integer $c$ (it clearly can't be negative). Then
$$t_n=sqrtf(2^n)=sqrtcg(2^n)^2+h(2^n)=sqrtcg(2^n)+O(2^-n)$$. Yet $g(2^n)=sum_k=0^d/2c_k (2^k)^n$ is a rational power sum in $2^0,ldots,2^d/2$, so because $(x-2^0)cdots(x-2^d/2)inmathbbZ[x]$ has coefficients independent of $n$, $t_n$ satisfies a linear recurrence of order $1+d/2$ with integer coefficients up to an error of $o(1)$. But $t_ninmathbbZforallnge1$, so for sufficiently large $nge N$, $t_n$ satisfies the linear recurrence exactly, i.e. there exists a polynomial $p(x)$ such that $t_n=p(2^n)$ for all $nge N$ and thus $f(x)=p(x)^2$ for all $x$. But $g$ is unique up to sign, so $p(x)^2=cq(x)^2$ and considering $x=2^n$ for sufficiently large $n$, $c$ must be a square, i.e. $p(x)inmathbbQ[x]$ as desired.
Now if $deg f$ is odd, then by the previous case there exist polynomials $g_1,g_2inmathbbQ[x]$ such that $f(x^2)=g_1(x)^2$ and $f(2x^2)=g_2(x)^2$, so $g_1(xsqrt2)=pm g_2(x)$, which contradicts rationality by equating coefficients.
Can I get a clear understanding of the solution? I don't think I get it well enough, at least from the $(x-2^0)(x-2^1)cdots in mathbbZ[x]$ and the linear recurrence part. Also, at the initial stage, the user claims that $t_n=sqrtf(2^n)=sqrtcg(2^n)^2+h(2^n)=sqrtcg(2^n)+O(2^-n)$. How is it $O(2^-n)$? Isn't it supposed to be $Oleft(2^fracn(d-2)4right)$?
polynomials
asked Jul 16 at 18:17
Mathejunior
1,460321
 |Â
show 3 more comments
up vote
5
down vote
favorite
If $fin mathbbZ[x]$ is a polynomial and $f(2^n)$ is a perfect square for all $n$, then there is a $gin mathbbZ[x]$ such that $f=g^2$
I understand that there might be an issue with the problem statement but I don't know anything further.
Here's a link that might help (related problem).
EDIT : I see the exact problem posted in AoPS long time ago. I couldn't understand the solution posted there.
I'm quoting user Math154's solution :
Multiplying by the square of $f$'s denominator if necessary, WLOG $finmathbbZ[x]$ and $t_n=sqrtf(2^n)inmathbbZ^+$ for all $nge1$.
First suppose that $d=deg f$ is even, so $f(x)=cg(x)^2+h(x)$ for polynomials $g,hinmathbbQ[x]$ with $degg=d/2$ and $degh<d/2$ and a positive integer $c$ (it clearly can't be negative). Then
$$t_n=sqrtf(2^n)=sqrtcg(2^n)^2+h(2^n)=sqrtcg(2^n)+O(2^-n)$$. Yet $g(2^n)=sum_k=0^d/2c_k (2^k)^n$ is a rational power sum in $2^0,ldots,2^d/2$, so because $(x-2^0)cdots(x-2^d/2)inmathbbZ[x]$ has coefficients independent of $n$, $t_n$ satisfies a linear recurrence of order $1+d/2$ with integer coefficients up to an error of $o(1)$. But $t_ninmathbbZforallnge1$, so for sufficiently large $nge N$, $t_n$ satisfies the linear recurrence exactly, i.e. there exists a polynomial $p(x)$ such that $t_n=p(2^n)$ for all $nge N$ and thus $f(x)=p(x)^2$ for all $x$. But $g$ is unique up to sign, so $p(x)^2=cq(x)^2$ and considering $x=2^n$ for sufficiently large $n$, $c$ must be a square, i.e. $p(x)inmathbbQ[x]$ as desired.
Now if $deg f$ is odd, then by the previous case there exist polynomials $g_1,g_2inmathbbQ[x]$ such that $f(x^2)=g_1(x)^2$ and $f(2x^2)=g_2(x)^2$, so $g_1(xsqrt2)=pm g_2(x)$, which contradicts rationality by equating coefficients.
Can I get a clear understanding of the solution? I don't think I get it well enough, at least from the $(x-2^0)(x-2^1)cdots in mathbbZ[x]$ and the linear recurrence part. Also, at the initial stage, the user claims that $t_n=sqrtf(2^n)=sqrtcg(2^n)^2+h(2^n)=sqrtcg(2^n)+O(2^-n)$. How is it $O(2^-n)$? Isn't it supposed to be $Oleft(2^fracn(d-2)4right)$?
polynomials
asked Jul 16 at 18:17
Mathejunior
1,460321
Why would $g=0$? We can have e.g. $f(x)=x^2$ and then $gneq 0$.
– Wojowu
Jul 16 at 18:27
@Wojowu Oh, okay I see. That was stupid of me to think so. Edited.
– Mathejunior
Jul 16 at 18:28
I think that if $f(x)=h(x)+c$ for some non negative $c$, then $g$ will be $0$.
– Mathejunior
Jul 16 at 18:30
Why can't you have $h(x)=x^2-1$ and $c=1$?
– Wojowu
Jul 16 at 18:34
@Wojowu I actually meant something of the form $f(x)=xh(x)+c$. Just to be precise.
– Mathejunior
Jul 16 at 18:38
 |Â
show 3 more comments
up vote
5
down vote
favorite
up vote
5
down vote
favorite
If $fin mathbbZ[x]$ is a polynomial and $f(2^n)$ is a perfect square for all $n$, then there is a $gin mathbbZ[x]$ such that $f=g^2$
I understand that there might be an issue with the problem statement but I don't know anything further.
Here's a link that might help (related problem).
EDIT : I see the exact problem posted in AoPS long time ago. I couldn't understand the solution posted there.
I'm quoting user Math154's solution :
Multiplying by the square of $f$'s denominator if necessary, WLOG $finmathbbZ[x]$ and $t_n=sqrtf(2^n)inmathbbZ^+$ for all $nge1$.
First suppose that $d=deg f$ is even, so $f(x)=cg(x)^2+h(x)$ for polynomials $g,hinmathbbQ[x]$ with $degg=d/2$ and $degh<d/2$ and a positive integer $c$ (it clearly can't be negative). Then
$$t_n=sqrtf(2^n)=sqrtcg(2^n)^2+h(2^n)=sqrtcg(2^n)+O(2^-n)$$. Yet $g(2^n)=sum_k=0^d/2c_k (2^k)^n$ is a rational power sum in $2^0,ldots,2^d/2$, so because $(x-2^0)cdots(x-2^d/2)inmathbbZ[x]$ has coefficients independent of $n$, $t_n$ satisfies a linear recurrence of order $1+d/2$ with integer coefficients up to an error of $o(1)$. But $t_ninmathbbZforallnge1$, so for sufficiently large $nge N$, $t_n$ satisfies the linear recurrence exactly, i.e. there exists a polynomial $p(x)$ such that $t_n=p(2^n)$ for all $nge N$ and thus $f(x)=p(x)^2$ for all $x$. But $g$ is unique up to sign, so $p(x)^2=cq(x)^2$ and considering $x=2^n$ for sufficiently large $n$, $c$ must be a square, i.e. $p(x)inmathbbQ[x]$ as desired.
Now if $deg f$ is odd, then by the previous case there exist polynomials $g_1,g_2inmathbbQ[x]$ such that $f(x^2)=g_1(x)^2$ and $f(2x^2)=g_2(x)^2$, so $g_1(xsqrt2)=pm g_2(x)$, which contradicts rationality by equating coefficients.
Can I get a clear understanding of the solution? I don't think I get it well enough, at least from the $(x-2^0)(x-2^1)cdots in mathbbZ[x]$ and the linear recurrence part. Also, at the initial stage, the user claims that $t_n=sqrtf(2^n)=sqrtcg(2^n)^2+h(2^n)=sqrtcg(2^n)+O(2^-n)$. How is it $O(2^-n)$? Isn't it supposed to be $Oleft(2^fracn(d-2)4right)$?
polynomials
asked Jul 16 at 18:17
Mathejunior
1,460321
If $fin mathbbZ[x]$ is a polynomial and $f(2^n)$ is a perfect square for all $n$, then there is a $gin mathbbZ[x]$ such that $f=g^2$
I understand that there might be an issue with the problem statement but I don't know anything further.
Here's a link that might help (related problem).
EDIT : I see the exact problem posted in AoPS long time ago. I couldn't understand the solution posted there.
I'm quoting user Math154's solution :
Multiplying by the square of $f$'s denominator if necessary, WLOG $finmathbbZ[x]$ and $t_n=sqrtf(2^n)inmathbbZ^+$ for all $nge1$.
First suppose that $d=deg f$ is even, so $f(x)=cg(x)^2+h(x)$ for polynomials $g,hinmathbbQ[x]$ with $degg=d/2$ and $degh<d/2$ and a positive integer $c$ (it clearly can't be negative). Then
$$t_n=sqrtf(2^n)=sqrtcg(2^n)^2+h(2^n)=sqrtcg(2^n)+O(2^-n)$$. Yet $g(2^n)=sum_k=0^d/2c_k (2^k)^n$ is a rational power sum in $2^0,ldots,2^d/2$, so because $(x-2^0)cdots(x-2^d/2)inmathbbZ[x]$ has coefficients independent of $n$, $t_n$ satisfies a linear recurrence of order $1+d/2$ with integer coefficients up to an error of $o(1)$. But $t_ninmathbbZforallnge1$, so for sufficiently large $nge N$, $t_n$ satisfies the linear recurrence exactly, i.e. there exists a polynomial $p(x)$ such that $t_n=p(2^n)$ for all $nge N$ and thus $f(x)=p(x)^2$ for all $x$. But $g$ is unique up to sign, so $p(x)^2=cq(x)^2$ and considering $x=2^n$ for sufficiently large $n$, $c$ must be a square, i.e. $p(x)inmathbbQ[x]$ as desired.
Now if $deg f$ is odd, then by the previous case there exist polynomials $g_1,g_2inmathbbQ[x]$ such that $f(x^2)=g_1(x)^2$ and $f(2x^2)=g_2(x)^2$, so $g_1(xsqrt2)=pm g_2(x)$, which contradicts rationality by equating coefficients.
Can I get a clear understanding of the solution? I don't think I get it well enough, at least from the $(x-2^0)(x-2^1)cdots in mathbbZ[x]$ and the linear recurrence part. Also, at the initial stage, the user claims that $t_n=sqrtf(2^n)=sqrtcg(2^n)^2+h(2^n)=sqrtcg(2^n)+O(2^-n)$. How is it $O(2^-n)$? Isn't it supposed to be $Oleft(2^fracn(d-2)4right)$?
polynomials
asked Jul 16 at 18:17
Mathejunior
1,460321
edited Jul 17 at 16:02
asked Jul 16 at 18:17
Mathejunior
1,460321
asked Jul 16 at 18:17
Mathejunior
1,460321
asked Jul 16 at 18:17
Mathejunior
1,460321
1,460321
Why would $g=0$? We can have e.g. $f(x)=x^2$ and then $gneq 0$.
– Wojowu
Jul 16 at 18:27
@Wojowu Oh, okay I see. That was stupid of me to think so. Edited.
– Mathejunior
Jul 16 at 18:28
I think that if $f(x)=h(x)+c$ for some non negative $c$, then $g$ will be $0$.
– Mathejunior
Jul 16 at 18:30
Why can't you have $h(x)=x^2-1$ and $c=1$?
– Wojowu
Jul 16 at 18:34
@Wojowu I actually meant something of the form $f(x)=xh(x)+c$. Just to be precise.
– Mathejunior
Jul 16 at 18:38
 |Â
show 3 more comments
Why would $g=0$? We can have e.g. $f(x)=x^2$ and then $gneq 0$.
– Wojowu
Jul 16 at 18:27
@Wojowu Oh, okay I see. That was stupid of me to think so. Edited.
– Mathejunior
Jul 16 at 18:28
I think that if $f(x)=h(x)+c$ for some non negative $c$, then $g$ will be $0$.
– Mathejunior
Jul 16 at 18:30
Why can't you have $h(x)=x^2-1$ and $c=1$?
– Wojowu
Jul 16 at 18:34
@Wojowu I actually meant something of the form $f(x)=xh(x)+c$. Just to be precise.
– Mathejunior
Jul 16 at 18:38
Why would $g=0$? We can have e.g. $f(x)=x^2$ and then $gneq 0$.
– Wojowu
Jul 16 at 18:27
Why would $g=0$? We can have e.g. $f(x)=x^2$ and then $gneq 0$.
– Wojowu
Jul 16 at 18:27
@Wojowu Oh, okay I see. That was stupid of me to think so. Edited.
– Mathejunior
Jul 16 at 18:28
@Wojowu Oh, okay I see. That was stupid of me to think so. Edited.
– Mathejunior
Jul 16 at 18:28
I think that if $f(x)=h(x)+c$ for some non negative $c$, then $g$ will be $0$.
– Mathejunior
Jul 16 at 18:30
I think that if $f(x)=h(x)+c$ for some non negative $c$, then $g$ will be $0$.
– Mathejunior
Jul 16 at 18:30
Why can't you have $h(x)=x^2-1$ and $c=1$?
– Wojowu
Jul 16 at 18:34
Why can't you have $h(x)=x^2-1$ and $c=1$?
– Wojowu
Jul 16 at 18:34
@Wojowu I actually meant something of the form $f(x)=xh(x)+c$. Just to be precise.
– Mathejunior
Jul 16 at 18:38
@Wojowu I actually meant something of the form $f(x)=xh(x)+c$. Just to be precise.
– Mathejunior
Jul 16 at 18:38
 |Â
show 3 more comments
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
In this answer I address the two potential issues you point out at the end of your question.
[1] Also, at the initial stage, the user claims ...
The estimate from Mean Value Theorem is:
$$ |f(x+h) - f(x)| leq sup_y|f'(y)| |h|$$
where the sup is over $y$ in between $x$ and $x+h$. Let "$ Alesssim B$" mean that $A ≤ C B$ for some unimportant constant $C>0$.
If $f$ is the square root function, $h = h(2^n)$, and $x=cg(2^n)^2 $, notice that
$|h(2^n)|lesssim 2^n(d/2-1)$, and $sup_y |f'(y)|lesssim frac1lesssim 2^-nd/2$, so we get the estimate
$$ left|sqrt cg(2^n)^2 + h(2^n) - sqrtcg(2^n)right| lesssim frac2^n(d/2 - 1)2^nd/2 = 2^-n$$
as claimed.
[2] the linear recurrence part...
You will need to know the basic theorem for higher order linear recurrences. Here's one version:
Theorem. Suppose we had the "characteristic polynomial" expressed in the following two ways, $$c(x) = x^K - alpha_1 x^K-1 - dots - alpha_K = (x-lambda_1)dots(x-lambda_K),$$ where $alpha_i,lambda_i$ are constants, then for any constants $C_1,dots,C_K$, the sequence
$$ a_n = sum_i=1^K C_i lambda_i^n$$
is a solution to the recurrence
$$ a_n = alpha_1 a_n-1 + dots + alpha_K alpha_n-K $$
Proof. Since the recurrence is linear, linear combinations of solutions are also solutions. So it suffices to check that each $ lambda_i^n$ is a solution. But this is obvious, as $lambda_i^n-Kc(lambda_i) = 0$.
To apply this: what the answer is trying to say is that $g(2^n)$ solves a recurrence exactly. Since $g(2^n)$ is some combination of $1,dots,(2^d/2)^n$, let $lambda_i = 2^i-1$, $i=1,dots,K=d/2+1$, the corresponding characteristic polynomial is $(x-1)dots(x-2^d/2)$ as the user hinted towards, and the recurrence could even be written down explicitly.
answered Jul 17 at 17:02
Calvin Khor
8,15911133
Wow, that's quite an awesome explanation! That's exactly what I'd asked for. Thank you
– Mathejunior
Jul 17 at 19:51
@Mathejunior you're welcome :)
– Calvin Khor
Jul 17 at 20:18
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
In this answer I address the two potential issues you point out at the end of your question.
[1] Also, at the initial stage, the user claims ...
The estimate from Mean Value Theorem is:
$$ |f(x+h) - f(x)| leq sup_y|f'(y)| |h|$$
where the sup is over $y$ in between $x$ and $x+h$. Let "$ Alesssim B$" mean that $A ≤ C B$ for some unimportant constant $C>0$.
If $f$ is the square root function, $h = h(2^n)$, and $x=cg(2^n)^2 $, notice that
$|h(2^n)|lesssim 2^n(d/2-1)$, and $sup_y |f'(y)|lesssim frac1lesssim 2^-nd/2$, so we get the estimate
$$ left|sqrt cg(2^n)^2 + h(2^n) - sqrtcg(2^n)right| lesssim frac2^n(d/2 - 1)2^nd/2 = 2^-n$$
as claimed.
[2] the linear recurrence part...
You will need to know the basic theorem for higher order linear recurrences. Here's one version:
Theorem. Suppose we had the "characteristic polynomial" expressed in the following two ways, $$c(x) = x^K - alpha_1 x^K-1 - dots - alpha_K = (x-lambda_1)dots(x-lambda_K),$$ where $alpha_i,lambda_i$ are constants, then for any constants $C_1,dots,C_K$, the sequence
$$ a_n = sum_i=1^K C_i lambda_i^n$$
is a solution to the recurrence
$$ a_n = alpha_1 a_n-1 + dots + alpha_K alpha_n-K $$
Proof. Since the recurrence is linear, linear combinations of solutions are also solutions. So it suffices to check that each $ lambda_i^n$ is a solution. But this is obvious, as $lambda_i^n-Kc(lambda_i) = 0$.
To apply this: what the answer is trying to say is that $g(2^n)$ solves a recurrence exactly. Since $g(2^n)$ is some combination of $1,dots,(2^d/2)^n$, let $lambda_i = 2^i-1$, $i=1,dots,K=d/2+1$, the corresponding characteristic polynomial is $(x-1)dots(x-2^d/2)$ as the user hinted towards, and the recurrence could even be written down explicitly.
answered Jul 17 at 17:02
Calvin Khor
8,15911133
Wow, that's quite an awesome explanation! That's exactly what I'd asked for. Thank you
– Mathejunior
Jul 17 at 19:51
@Mathejunior you're welcome :)
– Calvin Khor
Jul 17 at 20:18
add a comment |Â
up vote
2
down vote
accepted
In this answer I address the two potential issues you point out at the end of your question.
[1] Also, at the initial stage, the user claims ...
The estimate from Mean Value Theorem is:
$$ |f(x+h) - f(x)| leq sup_y|f'(y)| |h|$$
where the sup is over $y$ in between $x$ and $x+h$. Let "$ Alesssim B$" mean that $A ≤ C B$ for some unimportant constant $C>0$.
If $f$ is the square root function, $h = h(2^n)$, and $x=cg(2^n)^2 $, notice that
$|h(2^n)|lesssim 2^n(d/2-1)$, and $sup_y |f'(y)|lesssim frac1lesssim 2^-nd/2$, so we get the estimate
$$ left|sqrt cg(2^n)^2 + h(2^n) - sqrtcg(2^n)right| lesssim frac2^n(d/2 - 1)2^nd/2 = 2^-n$$
as claimed.
[2] the linear recurrence part...
You will need to know the basic theorem for higher order linear recurrences. Here's one version:
Theorem. Suppose we had the "characteristic polynomial" expressed in the following two ways, $$c(x) = x^K - alpha_1 x^K-1 - dots - alpha_K = (x-lambda_1)dots(x-lambda_K),$$ where $alpha_i,lambda_i$ are constants, then for any constants $C_1,dots,C_K$, the sequence
$$ a_n = sum_i=1^K C_i lambda_i^n$$
is a solution to the recurrence
$$ a_n = alpha_1 a_n-1 + dots + alpha_K alpha_n-K $$
Proof. Since the recurrence is linear, linear combinations of solutions are also solutions. So it suffices to check that each $ lambda_i^n$ is a solution. But this is obvious, as $lambda_i^n-Kc(lambda_i) = 0$.
To apply this: what the answer is trying to say is that $g(2^n)$ solves a recurrence exactly. Since $g(2^n)$ is some combination of $1,dots,(2^d/2)^n$, let $lambda_i = 2^i-1$, $i=1,dots,K=d/2+1$, the corresponding characteristic polynomial is $(x-1)dots(x-2^d/2)$ as the user hinted towards, and the recurrence could even be written down explicitly.
answered Jul 17 at 17:02
Calvin Khor
8,15911133
Wow, that's quite an awesome explanation! That's exactly what I'd asked for. Thank you
– Mathejunior
Jul 17 at 19:51
@Mathejunior you're welcome :)
– Calvin Khor
Jul 17 at 20:18
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
In this answer I address the two potential issues you point out at the end of your question.
[1] Also, at the initial stage, the user claims ...
The estimate from Mean Value Theorem is:
$$ |f(x+h) - f(x)| leq sup_y|f'(y)| |h|$$
where the sup is over $y$ in between $x$ and $x+h$. Let "$ Alesssim B$" mean that $A ≤ C B$ for some unimportant constant $C>0$.
If $f$ is the square root function, $h = h(2^n)$, and $x=cg(2^n)^2 $, notice that
$|h(2^n)|lesssim 2^n(d/2-1)$, and $sup_y |f'(y)|lesssim frac1lesssim 2^-nd/2$, so we get the estimate
$$ left|sqrt cg(2^n)^2 + h(2^n) - sqrtcg(2^n)right| lesssim frac2^n(d/2 - 1)2^nd/2 = 2^-n$$
as claimed.
[2] the linear recurrence part...
You will need to know the basic theorem for higher order linear recurrences. Here's one version:
Theorem. Suppose we had the "characteristic polynomial" expressed in the following two ways, $$c(x) = x^K - alpha_1 x^K-1 - dots - alpha_K = (x-lambda_1)dots(x-lambda_K),$$ where $alpha_i,lambda_i$ are constants, then for any constants $C_1,dots,C_K$, the sequence
$$ a_n = sum_i=1^K C_i lambda_i^n$$
is a solution to the recurrence
$$ a_n = alpha_1 a_n-1 + dots + alpha_K alpha_n-K $$
Proof. Since the recurrence is linear, linear combinations of solutions are also solutions. So it suffices to check that each $ lambda_i^n$ is a solution. But this is obvious, as $lambda_i^n-Kc(lambda_i) = 0$.
To apply this: what the answer is trying to say is that $g(2^n)$ solves a recurrence exactly. Since $g(2^n)$ is some combination of $1,dots,(2^d/2)^n$, let $lambda_i = 2^i-1$, $i=1,dots,K=d/2+1$, the corresponding characteristic polynomial is $(x-1)dots(x-2^d/2)$ as the user hinted towards, and the recurrence could even be written down explicitly.
answered Jul 17 at 17:02
Calvin Khor
8,15911133
In this answer I address the two potential issues you point out at the end of your question.
[1] Also, at the initial stage, the user claims ...
The estimate from Mean Value Theorem is:
$$ |f(x+h) - f(x)| leq sup_y|f'(y)| |h|$$
where the sup is over $y$ in between $x$ and $x+h$. Let "$ Alesssim B$" mean that $A ≤ C B$ for some unimportant constant $C>0$.
If $f$ is the square root function, $h = h(2^n)$, and $x=cg(2^n)^2 $, notice that
$|h(2^n)|lesssim 2^n(d/2-1)$, and $sup_y |f'(y)|lesssim frac1lesssim 2^-nd/2$, so we get the estimate
$$ left|sqrt cg(2^n)^2 + h(2^n) - sqrtcg(2^n)right| lesssim frac2^n(d/2 - 1)2^nd/2 = 2^-n$$
as claimed.
[2] the linear recurrence part...
You will need to know the basic theorem for higher order linear recurrences. Here's one version:
Theorem. Suppose we had the "characteristic polynomial" expressed in the following two ways, $$c(x) = x^K - alpha_1 x^K-1 - dots - alpha_K = (x-lambda_1)dots(x-lambda_K),$$ where $alpha_i,lambda_i$ are constants, then for any constants $C_1,dots,C_K$, the sequence
$$ a_n = sum_i=1^K C_i lambda_i^n$$
is a solution to the recurrence
$$ a_n = alpha_1 a_n-1 + dots + alpha_K alpha_n-K $$
Proof. Since the recurrence is linear, linear combinations of solutions are also solutions. So it suffices to check that each $ lambda_i^n$ is a solution. But this is obvious, as $lambda_i^n-Kc(lambda_i) = 0$.
To apply this: what the answer is trying to say is that $g(2^n)$ solves a recurrence exactly. Since $g(2^n)$ is some combination of $1,dots,(2^d/2)^n$, let $lambda_i = 2^i-1$, $i=1,dots,K=d/2+1$, the corresponding characteristic polynomial is $(x-1)dots(x-2^d/2)$ as the user hinted towards, and the recurrence could even be written down explicitly.
answered Jul 17 at 17:02
Calvin Khor
8,15911133
edited Jul 17 at 18:26
answered Jul 17 at 17:02
Calvin Khor
8,15911133
answered Jul 17 at 17:02
Calvin Khor
8,15911133
answered Jul 17 at 17:02
Calvin Khor
8,15911133
8,15911133
Wow, that's quite an awesome explanation! That's exactly what I'd asked for. Thank you
– Mathejunior
Jul 17 at 19:51
@Mathejunior you're welcome :)
– Calvin Khor
Jul 17 at 20:18
add a comment |Â
Wow, that's quite an awesome explanation! That's exactly what I'd asked for. Thank you
– Mathejunior
Jul 17 at 19:51
@Mathejunior you're welcome :)
– Calvin Khor
Jul 17 at 20:18
Wow, that's quite an awesome explanation! That's exactly what I'd asked for. Thank you
– Mathejunior
Jul 17 at 19:51
Wow, that's quite an awesome explanation! That's exactly what I'd asked for. Thank you
– Mathejunior
Jul 17 at 19:51
@Mathejunior you're welcome :)
– Calvin Khor
Jul 17 at 20:18
@Mathejunior you're welcome :)
– Calvin Khor
Jul 17 at 20:18
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2853690%2fif-f-in-mathbbzx-is-a-polynomial-and-f2n-is-a-perfect-square-for-all%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Why would $g=0$? We can have e.g. $f(x)=x^2$ and then $gneq 0$.
– Wojowu
Jul 16 at 18:27
@Wojowu Oh, okay I see. That was stupid of me to think so. Edited.
– Mathejunior
Jul 16 at 18:28
I think that if $f(x)=h(x)+c$ for some non negative $c$, then $g$ will be $0$.
– Mathejunior
Jul 16 at 18:30
Why can't you have $h(x)=x^2-1$ and $c=1$?
– Wojowu
Jul 16 at 18:34
@Wojowu I actually meant something of the form $f(x)=xh(x)+c$. Just to be precise.
– Mathejunior
Jul 16 at 18:38