TITLE: Parametric solutions of Pell's equation
QUESTION [29 upvotes]: Given a positive integer $n$ which is not a perfect square, it is well-known that
Pell's equation $a^2 - nb^2 = 1$ is always solvable in non-zero integers $a$ and $b$.

Question: Let $n$ be a positive integer which is not a perfect square.
  Is there always a polynomial $D \in \mathbb{Z}[x]$ of degree $2$, an integer $k$ and
  nonzero polynomials $P, Q \in \mathbb{Z}[x]$ such that $D(k) = n$ and $P^2 - DQ^2 = 1$,
  where $a = P(k)$, $b = Q(k)$ is the fundamental solution of the equation
  $a^2 - nb^2 = 1$?
If yes, is there an upper bound on the degree of the polynomials $P$ and $Q$ --
  and if so, is it even true that the degree of $P$ is always $\leq 6$?

Example: Consider $n := 13$.
Putting $D_1 := 4x^2+4x+5$ and $D_2 := 25x^2-14x+2$, we have $D_1(1) = D_2(1) = 13$.
Now the fundamental solutions of the equations
$P_1^2 - D_1Q_1^2 = 1$ and $P_2^2 - D_2Q_2^2 = 1$ are given by

$P_1 := 32x^6+96x^5+168x^4+176x^3+120x^2+48x+9$,
$Q_1 := 16x^5+40x^4+56x^3+44x^2+20x+4$

and

$P_2 := 1250x^2-700x+99$,
$Q_2 := 250x-70$,

respectively. Therefore $n = 13$ belongs to at least $2$ different series whose solutions
have ${\rm deg}(P) = 6$ and ${\rm deg}(P) = 2$, respectively.
Examples for all non-square $n \leq 150$ can be found here.
Added on Feb 3, 2015: All what remains to be done in order to turn
Leonardo's answers into a complete answer to the question is to find out which values
the index of the group of units of $\mathbb{Z}[\sqrt{n}]$ in the group of units
of the ring of integers of the quadratic field $\mathbb{Q}(\sqrt{n})$
can take. This part is presumably not even really MO level, but it's just
not my field -- maybe someone knows the answer?
Added on Feb 14, 2015: As nobody has completed the answer so far, it seems
this may be less easy than I thought on a first glance.
Added on Feb 17, 2015: Leonardo Zapponi has given now a complete answer to
the question in this note.

REPLY [4 votes]: Here are some results concerning the degree of the polynomial $P$. We only treat the cases where $n$ is a positive, square-free integer congruent to $3$ modulo $4$, showing that the degree of $P$ is less than or equal to $2$.
We start by the weaker assumption that, given the positive integer $n$ and a solution $(a,b)$ of Pell's equation $a^2-nb^2=1$, there exist polynomials $D,P,Q\in\Bbb Q[X]$ and a rational number $k$ such that $P^2-DQ^2=1$, with $D(k)=n,P(k)=a$ and $Q(k)=b$. Let $d$ be the degree of $P$. As mentioned in my other post, and following the conventions and results in David Speyer's answer, there exist constants $\alpha\in\Bbb C$ and $\beta,\gamma\in\Bbb Q$, with $\alpha^2,\gamma^2\in\Bbb Q$ such that
$$\begin{cases}
P=\pm T_d\left(\alpha(X+\beta)\right),\\
Q=\gamma U_{d-1}\left(\alpha(X+\beta)\right),\\
D=\gamma^{-2}\left(\alpha^2(X+\beta)^2-1\right),
\end{cases}$$
where $T_d$ (resp. $U_d$) denotes the degree $d$ Chebyshev polynomial of the first kind (resp. of the second kind). From the hypothesis on $P$, we can assume $\beta=0$. We have the identity
$$T_d+U_{d-1}\sqrt{X^2-1}=\left(X+\sqrt{X^2-1}\right)^d,$$
which leads to
$$P+Q\sqrt{D}=\left(\alpha X+\sqrt{\alpha^2X^2-1}\right)^d.$$
If $d$ is odd then the explicit expression of $T_d$ shows that $\alpha$ (and therefore $\gamma$) is rational. Evaluating at $k$, we then obtain the identity
$$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^d,$$
with $u,v\in\Bbb Q$. It then follows that $u+v\sqrt{n}$ is a unit in the ring of integers of $\Bbb Q(\sqrt{n})$ and, since we are assuming $n\equiv3\pmod4$, the elements $u$ and $v$ are integers. In particular, for $d>1$, the couple $(a,b)$ cannot be a fundamental solution of Pell's equation.
From now on, we assume $d=2m$ even. For $\alpha\in\Bbb Q$, we proceed as above and deduce that $(a,b)$ cannot be a fundamental solution for $d>1$. Suppose then that $\alpha=\sqrt{w}$, we $w\in\Bbb Q$ not a square, so that $\gamma=t\alpha$, with $t\in\Bbb Q$. We have the relation
$$T_d+U_{d-1}\sqrt{X^2-1}=\left(X^2-1+2X\sqrt{X^2-1}\right)^m$$
and thus
$$P+Q\sqrt{D}=\left(\alpha^2X^2-1+2\alpha\sqrt{\alpha^2X^2-1}\right)^m.$$
Evaluating at $k$, we then easily obtain the identity
$$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^m,$$
with $u,v\in\Bbb Q$. Once again, for $m>1$, it then follows that the couple $(a,b)$ cannot be a fundamental solution, leading to the result.
A final remark: for general $n$, if $(a,b)$ is a fundamental solution then
$$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^r,$$
where $u+v\sqrt{n}$ is a fundamental unit of $\Bbb Q(\sqrt{n})$. For example, in Stefan Kohl's example for $n=13$, we have
$$649+180\sqrt{13}=\left(\frac{11}2+\frac32\sqrt{13}\right)^3.$$
I'm definitely not an expert on this subject, but the above discussion combined with an explicit bound for the integer $r$ would lead to a bound for the degree of $P$ and therefore give a complete answer to the second question.


TITLE: The pair $x_1$ , $x_2$ are Linearly Independent
QUESTION [1 upvotes]: Prove that if $x_1$ and $x_2$ are  eigenvectors  with different eigenvalues, then the pair $x_1$ and $x_2$ are linearly independent.
The way I went about this proof is by the contrapositive. So I am assuming that the eigenvalues are the same.
For some nonzero vectors $x_1$, $x_2 \in V$, $Ax_1 = \lambda_1x_1$ and $Ax_2 = \lambda_1x_2$ such that $A:V \rightarrow V$ and $\lambda_1 \in R$.
Therefore $x_1 = A^{-1}\lambda_1x_1$ and $x_2 = A^{-1}\lambda_1x_2$ and thus $x_1$ and $x_2$ can be written as a linear combination of each other.
Is this idea correct? Any help would appreciated.

REPLY [1 votes]: You are not assuming that $A$ is invertible here. Suppose $x_1$ and $x_2$ are linearly dependent, then $x_1=ax_2$ for some $a\not=0$. It turns out that $Ax_1 = A(ax_2)= aAx_2 = a\lambda_2x_2= \lambda_2x_1$, which gives a contradiction.

REPLY [0 votes]: Your approach may be okay, but $A$ may not be invertible as Gregory Grant pointed out in the comments.
One contrapositive approach is to assume that the two vectors are linearly dependent. Then, $\exists c\ne 0$ such that $x_1=c x_2\implies Ax_1=cAx_2\implies \lambda_1x_1=c\lambda_2x_2\implies \lambda_1=\lambda_2$ which is the negation of the hypothesis.


TITLE: What are the main uses of convex functions?
QUESTION [26 upvotes]: Up till now I have just learned that the concept of convexity in functions of one variable is used to complete the graphs of functions, meaning to locate points of inflexion and see if the graph is concave or convex in given intervals. Spivak's book mention that altough this is what we typically learn at calculus, the importance of this concept doesn't lie precisely on ploting graphs and it is really worth to assimilate the information. I'd like to know the main aplications of this concept and it's importance in general.

REPLY [5 votes]: Convex analysis has proven that in a certain sense, convexity is the next best thing to linearity. Basically, as soon as you allow inequalities in linear setting, you are immediately in the territory of convex analysis. So convexity arises naturally in the study of dual spaces and weak topologies. In fact, there is a tendency to give the name "convexity" to anything that is nicely compatible with variational minimization problems. On another note, convexity and monotonicity are two sides of the same coin. Importance of monotonicity is something that does not need too much convincing. This link has been exploited e.g. in nonlinear PDEs, such as the Monge-Ampere equations.


TITLE: Is my understanding of electric fields accurate?
QUESTION [2 upvotes]: Could someone please help me and let me know if the statements below are any accurate? I am struggling trying to understand what electric fields are and I could really use some help!

An electric field is a force that radiates away from protons and towards electrons.
Because atoms are the basic building blocks of ordinary matter, electric fields are always associated with atoms. In other words, we never refer to electric fields as being generated by lonely protons or lonely electrons floating somewhere in space, instead, we always refer to the electric field in atoms. That said, we could redefine statement 1 and say that an electric field is a force that radiates away from atoms with a lack of electrons and towards atoms with an excess of electrons.
Under normal conditions, the electric field between the atom’s protons and the atom’s electrons cancels out. When this happens, the atom is neutral (no charge), no electric field radiates in or out of the atom.
Under not so normal conditions, an atom will either lack electrons or have excess electrons, when this happens a "push and pull" electric field is formed between the atoms. This "push and pull" field is what makes electrons move from the negatively charged atom to the positively charge atom creating electric current.
As mentione before, an "push and pull" electric field is created between atom that lack electrons and those that have excess electrons, it does not matter what type of atoms they are, for example, if one atom of Oxygen is missing an electron and one atom of Calcium has an extra electron then an electric field will form between those atoms.
Electric fields are infinite. This means that an electric field will be formed between atoms with lack of electrons and atoms with excess electrons no matter how far apart they are. To be clear, even if the atoms are billions and billions of miles apart there will still be an electric field formed between them.
An electric field that forms between two atoms is what makes voltage happen. The closer the atoms are from each other the greater the voltage will be between them duet to thicker flux lines crossing each other.

Do my statements make any sense whatsoever or am I just embarrassing myself?
Thank you.

REPLY [4 votes]: Do my statements make any sense whatsoever or am I just embarrassing myself?

First of all, never be embarrased asking a question :) Though a quite long question, I will quickly go through your points:

An electric field is a force that radiates away from protons and towards electrons.

No, electric field and force is not the same. But you could though consider it a "force per charge", since they are related by $E=F/q$.
"Radiates" away is not a proper term. There is no radiation here.
Yes, the direction is correct (just a convention). But remember that this "direction" is just to tell the orientation of the effect the field might cause. If you put a positive charge in an electric field, it will be pushed along with the field line direction (because of the force in $E=F/q$); if you put a negative charge in, it will move the opposite way.

Because atoms are the basic building blocks of ordinary matter, electric fields are always associated with atoms. In other words, we never refer to electric fields as being generated by lonely protons or lonely electrons floating somewhere in space, instead, we always refer to the electric field in atoms. That said, we could redefine statement 1 and say that an electric field is a force that radiates away from atoms with a lack of electrons and towards atoms with an excess of electrons.

With the above corrections, yes, this will be the orientation of ions (charges atoms that are missing or have extra electrons).
But saying that "electric fields are always associated with atoms" is simply not true. In many cases in nature do we consider single positive or negative charges. For examples, consider semiconductor materials that are essential for much electronics, solar panels etc.

Under normal conditions, the electric field between the atom’s protons and the atom’s electrons cancels out. When this happens, the atom is neutral (no charge), no electric field radiates in or out of the atom.

Correct.

Under not so normal conditions, an atom will either lack electrons or have excess electrons, when this happens a "push and pull" electric field is formed between the atoms. This "push and pull" field is what makes electrons move from the negatively charged atom to the positively charge atom creating electric current.

Correct. Usually in a conducting wire for example, we don't consider the atomic structure but just the many free electrons. Yes, they are each associated with a mother-atom, but the "sea" of electrons that can concentrate in one end, causing an electric field, is usually described as what causes current to flow.

As mentione before, an "push and pull" electric field is created between atom that lack electrons and those that have excess electrons, it does not matter what type of atoms they are, for example, if one atom of Oxygen is missing an electron and one atom of Calcium has an extra electron then an electric field will form between those atoms.

Correct. A note: if you look at two seperated ions (charged atoms) they behave like this. If you on the contrary considers a bonding between two atoms where they share an electron pair e.g., then this pair is not necessarily  positioned exactly in the middle in between the two ions. Because of the "shape" of the atom and how tightly held the electron shells are, ions have different electronegativity - when you break a bond, the most electronegative atom is the one that will keep the electrons.
So, what you say is true, but if you get very close to the atoms or even mix the electron waves of two atoms, the distances to the positive cores and the remaining electrons of each atom makes it much more complicated, as you cannot just consider it a simple point-charge anymore. This is a topic of chemical bonds and only relevant in compounds.

Electric fields are infinite. This means that an electric field will be formed between atoms with lack of electrons and atoms with excess electrons no matter how far apart they are. To be clear, even if the atoms are billions and billions of miles apart there will still be an electric field formed between them.

Correct.
Another note: You always refer to two charged atoms at a time. While what you say is correct, it would still be true for just a single charge in space. This charge will by itself cause an electric field in it's surroundings theoretically spanning to infinity.

An electric field that forms between two atoms is what makes voltage happen. The closer the atoms are from each other the greater the voltage will be between them duet to thicker flux lines crossing each other.

Sort of correct. But let's clear one thing out here: What is voltage exactly?
Voltage is another word for difference in electric potential. Each point in space will have an electric potential is there is a charge somewhere. Electric potential $V$ is simply electric potential energy $U$ per charge $q$ that is located at that point and being pushed at, $V=U/q$.
A charge wants to move to a point of lower (electric) potential energy. Just like a ball on a high shelf will tend to roll down to lower (gravitational) potential energy. Electric potential can be found by:
$$V=\frac{1}{4 \pi \epsilon_0} \frac{Q}{r}$$
$Q$ is the charge that causes the field (not the charge that is being pushed at). If there is much negative charge in one area (like close to a negative ion) you will find the potential to be negative $V_n<0$ since the charge is negative, $q=-e$. Close to a positive charge the potential is positive $V_p>0$.

Now, postiive charge will have negative potential energy at a point of negative potential, because of $V=U/q$ (where you multiply the negative $V$ with the positive $q$). It will have positive potential energy at a point of positive potential. So it wants to move to the negative potential (towards the negative charge).
A negative charge on the contrary will have the highest potential energy at a point of negative potential. Again because of $V=U/q$ (you multiply the negative $V$ with the now negative $q$). So for the electron, the point of lowest potential energy is at the point positive potential, and it will move towards the positive charge.

And now, back to the term voltage $V$. Voltage simply means potential difference, $V= V_p-V_n$. making voltage happen is again an odd choice of words - voltage doesn't "happen", voltage just "is". And if you added a charge in this field it would move, which we can determine if we know the voltage.
Lastly, yes, voltage and electric field are related by $E=V/r$, where $r$ is the distance between the two points over which the voltage (caused by the field $E$) is measured.


TITLE: Understanding the Fourier transform of a signal already with amplitude and phase information
QUESTION [0 upvotes]: I'm from an image processing background and am working my way into optics. I'm working on phase retrieval problems, trying to understand the Gerchberg-Saxton algorithm. I found this video which is really great, but which made me realize I probably had some misconceptions regarding some of the physics going on. I would like to clear these up before going further, so apologies for the probably very confused question and maybe approximate vocabulary.
The setup in the video is as follows : some field (with amplitude and phase) is imaged on an image plane, where we get the image of the intensity of the field, but not the phase, and we would like to know that phase. So the field is also projected "in the far field", to get the image in the "Fourier plane".

I get the gist of the rest of the algorithm pretty well, which involves comparing images in the image plane and the Fourier plane, enforcing constraints on the amplitude to iteratively correct the phase.

but what I don't get - and I think this is probably my lack of knowledge regarding Fourier optics speaking - is what truly is the "Fourier transform" discussed here. From my image processing background, the Fourier transform decomposes an image, i.e. a real signal, function of space, into an amplitude and phase image in frequency space. Something like :

So, I first thought that the Fourier transform discussed here was decomposition happening between the "image plane"'s intensity and the "Fourier plane"'s intensity + amplitude, ie the red arrows I've added to the figure.

However, that doesn't seem right, because the phase information seems to be taken into account during the Fourier transform. But then, what does the transform indicated by the following red arrow mean ? The field has both phase and amplitude information : is it in frequency space ? does it carry the same information as the phase and amplitude of the Fourier transform (ie the two right images on the bottom row) ? What does it mean to take the Fourier transform of a such a signal ?

REPLY [1 votes]: A complex field $F$ is a function $F: \mathbb{R}^N \rightarrow \mathbb{C}$. i.e. it is a complex number defined at each point in $N$-dimensional space.
The Fourier transform takes a complex field $F(\mathbf{x})$ and maps it to a new complex field $\mathcal{FT}[F](\boldsymbol{\nu}) = \tilde{F}(\boldsymbol{\nu})$. It (and it's inverse) may be defined (up to various convention choices) as
\begin{align}
\mathcal{FT}[F](\boldsymbol{\nu}) = \tilde{F}(\boldsymbol{\nu}) =  \int_{x_1=-\infty}^{+\infty}\ldots\int_{x_N=-\infty}^{+\infty} F(\mathbf{x}) e^{-i2\pi \boldsymbol{\nu}\cdot\textbf{x}} dx_N\ldots dx_1\\
\mathcal{FT}^{-1}[\mathcal{FT}[F]](\textbf{x}) = \breve{F}(\textbf{x}) = \int_{x_1=-\infty}^{+\infty}\ldots\int_{x_N=-\infty}^{+\infty} F(\mathbf{x}) e^{+i2\pi \boldsymbol{\nu}\cdot\textbf{x}} dx_N\ldots dx_1\\
\end{align}
The content of the Fourier inversion theorem is that, for suitable functions $F$ (which includes many functions encountered in physics and signal processing) that $\breve{F}(\textbf{x}) = F(\textbf{x})$, i.e. that the inverse Fourier transform is in fact the inverse of Fourier transform.
In 2D we have
$$
\tilde{F}(\boldsymbol{\nu}) = \int_{x_1=-\infty}^{+\infty} \int_{x_2=-\infty}^{+\infty} F(\textbf{x})e^{-2\pi \boldsymbol{\nu}\cdot\textbf{x}}dx_1dx_2
$$
Ok, this is all well and good and already answers much of your question. It seems you are familiar with the Fourier transform of REAL functions or REAL fields and that the Fourier transform of a real field is a complex field, however, here, I have plainly told you that it is actually possible (and typical) to take the Fourier transform of complex fields. If $F$ is a real function then $\tilde{F}$ satisfies that $\tilde{F}(-\boldsymbol{\nu}) = \tilde{F}^*(\boldsymbol{\nu})$, but this relation does not hold for non-real input fields $F$.
Note that in general to determine $F(\textbf{x})$ from $\tilde{F}(\boldsymbol{\nu})$ it is necessary to perform the inverse Fourier transform which requires information about the phase of $\tilde{F}(\boldsymbol{\nu})$.
The Gerchberg-Saxton algorithm answers the question: Given only amplitude information about $\tilde{F}(\boldsymbol{\nu})$, i.e. $|\tilde{F}(\boldsymbol{\nu})|$, is it possible to determine $F(\textbf{x})$. It turns out the answer to this question is false as there are multiple fields $F$ that give rise to the same Fourier transform amplitude. But, the Gerchberg-Saxton algorithm gives us the somewhat surprising result that if we have knowledge of both $|F(\textbf{x})|$ and $|\tilde{F}(\boldsymbol{\nu})|$ that it IS indeed possible, using an iterative algorithm, to recover $F(\textbf{x})$. This result is very useful precisely because of the example given in the OP. It is often the case in both optical and electrical signal processing (especially optical) that it is easy to measure the amplitude of both a signal and it's Fourier transform while it is possible, but much more difficult, to measure both the amplitude and phase of a signal or it's Fourier transform.
I think this answers your main question about how you can take the Fourier tansform of a complex field and how that information plays into the Gerchberg-Saxton algorithm. There is a remaining question which is: "Why does allowing an optical field to propagate into the far field implement the complex Fourier transform on the input field?" However, (a) you did not ask that question and (b) that question is addressed elsewhere on this site and in other references so I will not address it here.


TITLE: What is the value of the inradius of triangle $PHQ$?
QUESTION [1 upvotes]: For refrence: The right triangle $ABC$, right at $B$, the height $BH$ is drawn. Let $P$ and $Q$ be the intersections of triangles $AHB$ and $BHC$,
$PQ$ intersects at $E$ the $BH$, where $\frac{BE}{EH} = 5\sqrt2$ and the inradius of the triangle $ABC$ measures $10$.
Calculate the inradius of triangle $PHQ$.(Answer: $1$)
My progress..It is a complicated drawing ..not to scale...
I found it a difficult question and didn't get much out of it.... Maybe there is some relationship between the inradius but I don't know
I I know this(by property): $ r_1+r_2+R = BH\\
r_1+r_2+10 = BH$
Also: $\triangle MPH \sim \triangle NQH \implies\\
\frac{r_1}{r_2} = \frac{PH}{QH}$
By Geogebra $\triangle PQH$ is right?? $\implies$ T.Poncelet: $PH+HQ = PQ+2r$
...

REPLY [2 votes]: As $\angle PHQ = 90^\circ$ and $HE$ is its angle bisector, the incenter of $\triangle PHQ$ must lie on the segment $HE$. We mark it as $I$.
Next we note that $PM = MH = r_1$ and $QN = NH = r_2$. That leads to $PH = r_1 \sqrt2, QH = r_2 \sqrt2$.
As $\triangle AHB \sim \triangle BHC$ and they are right triangles, their inradii must be in the ratio of their hypotenuse.
So, $ \displaystyle \frac{r_1}{r_2} = \frac{c}{a} ~ $. But in right triangle $\triangle PHQ$, we also have $ \displaystyle \frac{PH}{HQ} = \frac{r_1}{r_2}$.
So, $\triangle PHQ \sim \triangle ABC \sim \triangle AHB \sim \triangle BHC \implies \angle HPQ = \angle A$.
If $r$ is the inradius of $\triangle PHQ$, $HI = r \sqrt2$
Using similarity of triangles,
$ \displaystyle \frac{AH}{r_1} = \frac{PH}{r} \implies AH = \frac{\sqrt2 r_1^2}{r} $. Similarly, $\displaystyle CH = \frac{\sqrt2 r_2^2}{r}$
Adding, $ \displaystyle AC = \frac{2 (r_1^2 + r_2^2)}{r \sqrt2} = \frac{PQ^2}{r \sqrt2} \implies \frac{AC}{PQ} = \frac{PQ}{r \sqrt2}$
As $\dfrac{AC}{PQ} = \dfrac{10}{r}, PQ = 10 \sqrt2$
$PH + HQ - PQ = 2r \implies \sqrt2 (r_1 + r_2) - 10 \sqrt2 = 2 r$. Using $r_1 + r_2 = BH - 10$, we get $ ~ BH - 20 = \sqrt2 r$.
Given $PI$ is angle bisector of $\angle HPE$ and $\angle BPI = 90^\circ$ so it follows that pencil $P (HE, IB)$ is harmonic. So we have,
$\dfrac{HI}{IE} = \dfrac{HB}{BE}$
$\dfrac{HI}{HE-HI} = 1 + \dfrac{1}{5 \sqrt2}$
$ (10 \sqrt2 + 1) HI  = (5 \sqrt2 + 1) HE = BH$
$(20 + \sqrt2) r = BH = 20 + \sqrt2 r$
$ \implies r = 1$


TITLE: With $N$ a constant $>0$, show $\prod_{p<x}\frac{1}{p^{N+1}-1}>\frac{0.2}{\log^2 x}$.
QUESTION [5 upvotes]: Related.
Show that if $x$ is large enough,$$\prod_{\substack{p<x \\ p \ \text{prime}}}\frac{1}{p^{N+1}-1}>\frac{0.2}{\log^2 x}.$$
Speaking of which, Theorem 6.12, and maybe others, of this paper might be useful.
If $N$ cannot be arbitrarily large for the inequality to hold, any conditions for truthfulness regarding its value are welcome.

REPLY [1 votes]: Your inequality is equivalent to $$-\underset{p\leq x}{\sum}\log\left(p^{N+1}-1\right)>\log\left(0.2\right)-2\log\left(\log\left(x\right)\right).$$
 Now we have, for partial summation and Prime Number Theorem, that exists $c_{1},c_{2}>0$
  such that $$-\log\left(0.2\right)-\underset{p\leq x}{\sum}\log\left(p^{N+1}-1\right)<-\underset{p\leq x}{\sum}\log\left(p\right)=-\left(c_{1}x+c_{2}\frac{x}{\log\left(x\right)}+o\left(\frac{x}{\log\left(x\right)}\right)\right)<-cx<-2\log\left(\log\left(x\right)\right)$$
 for some $c>0$
  and $x$
  large enough. So it is false.


TITLE: Prove that the error covariance matrix of the Recursive Least Squares Estimation is positive definite
QUESTION [0 upvotes]: A linear recursive estimator can be written in the following form:
$$y_k=H_kx+v_k$$
$$\hat{x}_k=\hat{x}_{k-1}+K_k(y_k-H_k\hat{x}_{k-1})$$
Where $H_k$ is an $m\times{}n$ matrix, $K_k$ is $n\times{}m$ and is referred as the estimator matrix gain.
In addition, $y_k-H_k\hat{x}_{k-1}$ is the correction term of our estimate and modifies our past estimate $\hat{x}_{k-1}$ to $\hat{x}$. $v_k$ is the noise on our meassurement with mean equal to zero.
The current estimation error is: $\epsilon{}_k=x-\hat{x}_k$ and after substituting $\hat{x}_k$ and some simplifications in the expresion we get:
$$\epsilon_k=(I-K_kH_k)\epsilon_{k-1}-K_kv_k$$ Where $I$ is the $n\times{}n$ identity matrix.
Next, we define the estimation-error covariance  $n\times{}n$ matrix $P_k=E[\epsilon_k\epsilon_{k}^T]$and the noise covariance $m\times{}m$ matrix $R_k=E[v_kv_{k}^T]$. Moreover, substituting the definition of $\epsilon_k$ in our $P_k$ definition and after some algebraic simplifications we get:
$$P_k=(I-K_kH_k)P_{k-1}(I-K_kH_k)^T+K_kR_kK_k^T$$
We have to prove that $P_k$ is always positive definite if $P_{k-1}$ and $R_k$ are positive definite.

REPLY [0 votes]: If the matrix is $I-K_kH_k$ is invertible, then the result follows from the fact that the matrix $(I-K_kH_k)P_{k-1}(I-K_kH_k)^T$ is congruent to $P_{k-1}$. So, $P_{k-1}$ positive definite is equivalent to $(I-K_kH_k)P_{k-1}(I-K_kH_k)^T$ positive definite.
Now assume that $I-K_kH_k$ is singular and let $\ell_k$ be the algebraic multiplicity of the zero eigenvalue (which we assume to be equal to the geometric multiplicity). So, let $V\in\mathbb{R}^{n\times \ell_k}$, full rank, such that $(I-K_kH_k)^TV_k=0$ and $V_k^TV_k=I_{\ell_k}$. Let $U_k$ be such that $M_k:=[U_k\ V_k]$ is a basis of $\mathbb{R}^n$.
Then, we obtain that
$$M_k^TP_kM_k=\begin{bmatrix}U_k^T(I-K_kH_k)P_{k-1}(I-K_kH_k)^TU_k & 0\\0 & 0\end{bmatrix}+\begin{bmatrix}U_k^T\\V_k^T\end{bmatrix}K_kR_kK_k^T\begin{bmatrix} U_k & V_k\end{bmatrix}.$$
The term $U_k^T(I-K_kH_k)P_{k-1}(I-K_kH_k)^TU_k$ is positive definite while the second term is positive semidefinite, so they need to compensate each other to make the sum positive definite. A necessary condition is that $V_k^TK_kR_kK_k^TV_k$ is positive definite.
To prove the sufficiency assume that $V_k^TK_kR_kK_k^TV_k$ is positive definite. Therefore, from a Schur complement argument, we have that
$$U_k^TD_kU_k-U_k^TD_kV_k(V_k^TD_kV_k)^{-1}V_k^TD_kU_k$$ is positive semidefinite where $D_k:=K_kR_kK_k^T$. Now, pick the sum of the matrices and perform a Schur complement to get
$$U_k^T(I-K_kH_k)P_{k-1}(I-K_kH_k)^TU_k+U_k^TD_kU_k-U_k^TD_kV_k(V_k^TD_kV_k)^{-1}V_k^TD_kU_k.$$
As the first term is positive definite and the second one is positive semidefinite, then the sum is positive definite, which proves that $P_k$ is positive definite if and only if $V_k^TK_kR_kK_k^TV_k$ is positive definite.