Math Challenge - March 2020

[Adesh]

Those classical theorems of calculus (IVT, MVT,...) aren't true if you restrict the domain to be only rational numbers.

For example, consider the function $f(x)=x^3-x$ Then $f(0)=f(1)=0$, but $f'(x)=3x^2-1$ does not have rational roots.

Yes, I agree with that. My proof of question 13 by Rolle's Theorem is flawed. Thank you @archaic and @Infrared

 

[Adesh]

One last try for question 13.

I have just remastered that quadratic proof which was flawed.
Here is my last try.

 

[julian]

You must have nightmares with BCH! I don't see a mistake, although I haven't checked the details of your last recursion which led to $5.01$.

The proof I have is essentially the same, only a bit lazier with the commutators and the estimation. I add it here, for the sake of completeness - and because it is not really different.

For a vector $\alpha \in \{\,0,1\,\}^n$ we define
$$
S(\alpha) := \prod_{k=1}^n A^{1-\alpha_k}B^{\alpha_k}
$$
Each of these vectors can be sorted in an ascending order in $n^2$ steps, e.g. with Bubble sort, until $S(\alpha_{Sort})=A^{n-|\alpha|}B^{|\alpha|}$ where every commutation between $A,B$ results in an additional term $[A,B]=AB-BA\,:$
$$
S(BA)-S(AB) = BA - AB = -[A,B]
$$
or with an example which needs more steps:
\begin{align*}
\begin{bmatrix}\alpha_0=(1,0,1,0)\\S(\alpha_0)=BABA \end{bmatrix} &\longrightarrow \begin{bmatrix}\alpha_1=(0,1,1,0)\\S(\alpha_1)=ABBA \end{bmatrix} \\
S(\alpha_0)-S(\alpha_1)&=(BA-AB)BA=-[A,B]BA \\
\begin{bmatrix}\alpha_1=(0,1,1,0)\\S(\alpha_1)=ABBA \end{bmatrix} &\longrightarrow \begin{bmatrix}\alpha_2=(0,1,0,1)\\S(\alpha_2)=ABAB \end{bmatrix} \\
S(\alpha_1)-S(\alpha_2)&=AB(BA-AB)=-AB[A,B] \\
\begin{bmatrix}\alpha_2=(0,1,0,1)\\S(\alpha_2)=ABAB \end{bmatrix} &\longrightarrow \begin{bmatrix}\alpha_3=(0,0,1,1)\\S(\alpha_3)=AABB \end{bmatrix} \\
S(\alpha_2)-S(\alpha_3)&=A(BA-AB)B =-A[A,B]B
\end{align*}
So every sorting step produces a factor $[A,B]$, which combined with the assumption $\|A\|,\|B\|\leq 1$ means $\|S(\alpha_k)-S(\alpha_{k+1})\| \leq \left\|\,[A,B]\,\right\|$ and
$$
\|S(\alpha)-S(\alpha_{Sort})\| \leq \sum_{k=0}^{n^2-1} \|S(\alpha_k)-S(\alpha_{k+1})\| \leq n^2\cdot \|\,[A,B]\,\|
$$
\begin{align*}
e^{A+B} &= \sum_{n=0}^\infty \dfrac{1}{n!} (A+B)^n=\sum_{n=0}^\infty \dfrac{1}{n!} \sum_{\alpha\in \{0,1\}^n} S(\alpha)\\
e^A\cdot e^B&= \left(\sum_{n=0}^\infty \dfrac{A^n}{n!}\right)\cdot\left(\sum_{n=0}^\infty \dfrac{B^n}{n!}\right)= \sum_{n=0}^\infty \sum_{k=0}^n \dfrac{A^{n-k}}{(n-k)!}\cdot \dfrac{B^k}{k!}\\
&=\sum_{n=0}^\infty \dfrac{1}{n!} \sum_{k=0}^n \binom{n}{k}A^{n-k}B^k = \sum_{n=0}^\infty \dfrac{1}{n!} \sum_{\alpha\in \{0,1\}^n} A^{n-|\alpha|}B^{|\alpha|}\\
&= \sum_{n=0}^\infty \dfrac{1}{n!} \sum_{\alpha\in \{0,1\}^n} S(\alpha_{Sort})
\end{align*}
With these equations we get
\begin{align*}
\|\;e^{A+B}-e^A \cdot e^B\;\| &\leq \sum_{n=0}^\infty \dfrac{1}{n!} \sum_{\alpha\in \{0,1\}^n} \|\;S(\alpha)-S(\alpha_{Sort})\;\|\\
& \leq \sum_{n=0}^\infty \dfrac{2^n}{n!} \cdot n^2\cdot \|\,[A,B]\,\|\\
&= 6e^2 \cdot \|\,[A,B]\,\|
\end{align*}

So this Bubble sort thing...Say there are $n$ positions for the $0$'s and $1$'s. A first cycle of comparisons, where you compare every pair of adjacent elements and swaps their positions :

\begin{align*}
(\underbrace{1,0},0,1 \dots, 0,0) & \rightarrow (0,1,0,1 \dots, 0,0)\\
(0, \underbrace{1,0},1 \dots, 0,0) & \rightarrow (0,0,1,1 \dots, 0,0)\\
(0, 0,\underbrace{1,1} \dots, 0,0) & \rightarrow (0,0,1,1 \dots, 0,0)\\
\vdots \\
(0, 0,1,1, \dots, \underbrace{1,0}) & \rightarrow (0,0,1,1, \dots, 0,1)
\end{align*}

inevitably leads to a $1$ in the last position after $n-1$ comparisons (unless they are all $0$). Meaning in a second cycle we need only consider $n-2$ comparisons. In a third cycle we need only consider $n-3$ comparisons. And so on. The total number of comparisons needed is then $(n-1)+ (n-2) + \cdots 1 = {n(n-1) \over 2}$. You can then say:

\begin{align*}
\|\;e^{A+B}-e^A \cdot e^B\;\| & \leq \sum_{n=0}^\infty \dfrac{2^n}{n!} \cdot {n(n-1) \over 2} \cdot \|\,[A,B]\,\|\\
&= 2e^2 \cdot \|\,[A,B]\,\| .
\end{align*}

Is this right?

 

[fresh_42]

Seems right, but as mentioned earlier, this was only a step towards Trotter's formula in problem 10. For its proof we only need a finite value, so there isn't any optimization on the sorting algorithm. $n^2$ is a trivial upper bound, not the lowest upper bound.

 

[Not anonymous]

5. Find the area of the shape $T$ which is surrounded by the line $|a_1 x + b_1 y + c_1| + |a_2 x + b_2 y + c_2| = m , m \gt 0$ (given that $a_1 b_2 - a_2 b_1 \neq 0$). (QQ)

Spoiler: Question 5

The solution of the equation $|a_1 x + b_1 y + c_1| + |a_2 x + b_2 y + c_2| = m , m \gt 0$ consists of points lying on 4 line segments that form a parallelogram. The vertices of this parallelogram are defined by intersection between the lines $|a_1 x + b_1 y + c_1|= m, |a_1 x + b_1 y + c_1|= -m, |a_2 x + b_2 y + c_2|= m$ and $|a_2 x + b_2 y + c_2|= -m$, i.e. the enclosed shape $T$ is a parallelogram formed by finite area intersection between 2 infinite area regions, region 1 consisting of the all points between parallel lines $|a_1 x + b_1 y + c_1|= m$ and $|a_1 x + b_1 y + c_1|= -m$, and region 2 consisting of the all points between parallel lines $|a_2 x + b_2 y + c_2|= m$ and $|a_2 x + b_2 y + c_2|= -m$.

The area of this parallelogram can be found using the absolute value of cross product between 2 vectors that correspond to any pair of adjoining edges of the parallelogram and have the common as their source point. The value I get for area of $T$ by calculating this way is $\left| \dfrac {2m^2} {a_2 b_1 - a_1 b_2}\right|$

Some details on how I found that the enclosed shape is a parallelogram. Solution to $|a_1 x + b_1 y + c_1| + |a_2 x + b_2 y + c_2| = m$ is the set made of all possible solutions to the pair of equations $a_1 x + b_1 y + c_1 = z, a_2 x + b_2 y + c_2 = m - |z|$ and all possible solutions to the pair of equations $a_1 x + b_1 y + c_1 = z, a_2 x + b_2 y + c_2 = |z| - m$, both pairs evaluated for all $z \in [-m, m]$.

For the 1st pair, the solution for any fixed value of $z$ is of the form $y = \dfrac {a_1 c_2 - a_2 c_1 - a_1 m + a_2 z + a_1 |z|} {a_2 b_1 - a_1 b_2}$, $x = \dfrac {-b_2 z + b_2 c_1 - b_1 c_2 + b_1 m - b_1 |z|} { a_2 b_1 - a_1 b_2}$.
Considering separately values of $z \in [0,m]$ and $z \in [-m, 0)$, we find that overall solution for that equation pair consists of all points on the line segment between points (in $X-Y$ coordinates) between $p_1$ and $p_3$ and all points on the line segment between $p_1$ and $p_3$ where $p_1= \left( \dfrac {b_2 c_1 - b_1 c_2 + b_1 m} {a_2 b_1 - a_1 b_2}, \dfrac {a_1 c_2 - a_2 c_1 - a_1 m} {a_2 b_1 - a_1 b_2} \right)$, $p_2 = \left( \dfrac{-b_2 m + b_2 c_1 - b_1 c_2} {a_2 b_1 - a_1 b_2} , \dfrac {a_1 c_2 - a_2 c_1 + a_2 m} {a_2 b_1 - a_1 b_2} \right)$ and $p_3 = \left( \dfrac {b_2 m + b_2 c_1 - b_1 c_2} {a_2 b_1 - a_1 b_2}, \dfrac {a_1 c_2 - a_2 c_1 - a_2 m} {a_2 b_1 - a_1 b_2} \right)$. The 3 points correspond to values $0, m \text { and } -m \text { for } z$.

Similarly, we can calculate the solutions for the 2nd equation pair and we find that it too consists of points on 2 line segments and each segment includes either the point $p_2$ or point $p_3$ obtained for 1st equation pair and that the 4 line segments form a parallelogram can be confirmed by looking at the slopes of the 4 line segments - it consists of 2 pairs of parallel line segments and the pairs intersect each other.
If we compute $\vec A$ corresponding to vector from $p_1$ to $p_2$ and $\vec B$ corresponding to vector from $p_1$ to $p_3$ and calculate the cross product $\vec A \times \vec B$, we get the area of the enclosed parallelogram to be $\left| \dfrac {2m^2} {a_2 b_1 - a_1 b_2}\right|$

 

[Pony]

I don't like how the solution of the 2nd problem points to https://www.physicsforums.com/threads/math-challenge-march-2020.984960/page-2#post-6306971 . That answer is very misleading. It only contains the trivial part of the problem and it does not even notice that this problem may be very very very difficult. @suremarc can you edit your answer?

 

[suremarc]

I don't like how the solution of the 2nd problem points to https://www.physicsforums.com/threads/math-challenge-march-2020.984960/page-2#post-6306971 . That answer is very misleading. It only contains the trivial part of the problem and it does not even notice that this problem may be very very very difficult. @suremarc can you edit your answer?

I agree that the answer is misleading, since applying invariance of domain means you need only prove injectivity; in that case the proof can be stated in two lines...

Unfortunately, I can’t edit my post anymore, since editing is disabled after a certain period of time.

 

[fresh_42]

I don't like how the solution of the 2nd problem points to https://www.physicsforums.com/threads/math-challenge-march-2020.984960/page-2#post-6306971 . That answer is very misleading.

I agree that the answer is misleading, since applying invariance of domain means you need only prove injectivity; in that case the proof can be stated in two lines...

Unfortunately, I can’t edit my post anymore, since editing is disabled after a certain period of time.

I split the link to both posts.

 

[Hiero]

For problem 5,

Spoiler: Is this the answer?

$\text{Area}=(\frac{m}{a_1b_2-a_2b_1})^2\sqrt{(A_1^2+B_1^2)(A_2^2+B_2^2)-(A_1A_2+B_1B_2)^2}$
where $A_1=a_1+a_2$ and $A_2=a_2-a_1$ and likewise for B in terms of b

Sorry I didn’t simplify all the way or explain because it was tedious and I think I might’ve made an error.

 

[Infrared]

@archaic You have an algebra mistakes. You should have $3x_1^2=\frac{8q^2-p^2}{q^2}$. The approach is definitely fine though.

 

[suremarc]

4. Let $k$ be a field that is not algebraically closed. Let $n\geq 1$. Show that there exists a polynomial $p\in k[x_1,\ldots,x_n]$ that vanishes only at the origin $(0,\ldots,0)\in k^n$. (IR)

Spoiler: Solution

Since $k$ is not algebraically closed, we can find a polynomial $p\in k[x]$ with no zeroes.

Now we construct a new polynomial $p_h(x,y)$ by homogenizing: $p_h(x,y)=y^dp(\frac{x}{y})$, where $d$ is the degree of $p(x)$. One can show that this is a well-defined polynomial, and in addition it vanishes only at the origin: suppose $p_h(x_0,y_0)=0$. Clearly this implies that $y=0$: we have $p_h(x_0,y_0)=y_0^dp(\frac{x_0}{y_0})=0\Rightarrow y_0=0\lor p(\frac{x_0}{y_0})=0$. Since $p$ has no zeroes, it then must be true that $y_0=0$. But $p_h(x_0,0)=cx_0^d$ (the leading term) which only vanishes when $x_0=0$. Hence we have shown that $x_0=y_0=0$ and we are done.

Now we use $p_h$ to inductively prove the existence of polynomials in arbitrarily many variables which vanish only at 0. Suppose $Q(x_1,\ldots,x_n)$ vanishes only at 0. Then $Q(x_1,\ldots,p_h(x_n,x_{n+1}))$ is a polynomial in n+1 variables that vanishes only at 0, because $Q(x_1,\ldots,p_h(x_n,x_{n+1}))=0\iff x_1=\ldots=p_h(x_n,x_{n+1})=0$. But $p_h(x_n,x_{n+1})=0\iff x_n=x_{n+1}=0$.

We have shown that, if there exists a polynomial in n variables that vanishes only at 0, there also exists a polynomial in n+1 variables that vanishes only at 0. Taking the monomial $x$ for $n=1$ as the base case, this proves that there exist polynomials in any number of variables that vanish only at 0. $\square$

 

[Infrared]

@suremarc Looks perfectly correct to me!

I'll just remark that the converse is basically obvious: If $n>1$ and $p\in k[x_1,\ldots,x_n]$ vanishes only at a single point, then $k$ must not be algebraically closed. So this gives an equivalent condition for a field (not) being algebraically closed.

 

[QuantumQuest]

For problem 5,

Spoiler: Is this the answer?

$\text{Area}=(\frac{m}{a_1b_2-a_2b_1})^2\sqrt{(A_1^2+B_1^2)(A_2^2+B_2^2)-(A_1A_2+B_1B_2)^2}$
where $A_1=a_1+a_2$ and $A_2=a_2-a_1$ and likewise for B in terms of b

Sorry I didn’t simplify all the way or explain because it was tedious and I think I might’ve made an error.

You can see the correct answer in the spoiler of post #65 by Not anonymous. In any case I don't see how you reached your answer.

 

[Infrared]

Just to point out another way to do 65 since it's already been solved: Let $P$ be the region we want the area of. The transformation $(x,y)\mapsto (u,v)=(a_1x+b_1y+c_1,a_2x+b_2y+c_2)$ is diffeomorphism from $P$ to the region bounded to the square $|u|+|v|= m$. The Jacobian determinant $a_1b_2-a_2b_1$. The area of the square $|u|+|v|\leq m$ is $2m^2$, so by the change of variables formula,

$2m^2=\int_{|u|+|v|\leq m} du dv=\int_P |a_1b_2-a_2b_1| dx dy$

Dividing by the Jacobian gives the desired area of $P$. This is really the same as @Not anonymous's answer since computing the Jacobian is equivalent to taking a cross product, but maybe it's helpful to see anyway and shows the idea of the change of variables formula: applying a linear map to a region scales the area/volume by the determinant (and to the first order, applying a function is the same as multiplying by its Jacobian matrix, up to translations).

 

[Adesh]

@archaic You have an algebra mistakes. You should have $3x_1^2=\frac{8q^2-p^2}{q^2}$. The approach is definitely fine though.

Sir, I think it was my solution . It was a minor typo I think. Is everything all right except that typo?

 

[Infrared]

I still don't think it's right. It looks like to me that you're claiming that since $3$ divides $8q^2-p^2$, it must divide both $8q^2$ and $p^2.$ I don't see why this should be true without further argument. For example, $3$ divides $1+5$ but not $1$ or $5$.

Also, in the future, please write your solutions in your post- I'd rather not have to follow links.

 

[PeroK]

Generalisation:

Spoiler: Question 13

Let's look at $f(x) = x^3 - px$, where $p$ is prime.

We'll look for $f(x) = f(y)$, where $x = \frac a b, \ y = \frac c d$ are in the lowest form.
$$f(\frac a b) = f(\frac c d) \ \Rightarrow \ \frac{a(a^2 - pb^2)}{b^3} = \frac{c(c^2 - pd^2)}{d^3}$$

Note that $\frac{a(a^2 - pb^2)}{b^3}$ is also in its lowest form, so we have $b = d$. And:
$$a(a^2 - pb^2) = c(c^2 - pb^2) \ \Rightarrow \ a^2 + ac + c^2 = pb^2 \ \Rightarrow \ (2a+c)^2 = 4pb^2 - 3c^2$$
So, we need solutions to:
$$4pb^2 - n^2 = 3c^2$$
Where $n = 2a + c$.

We have solutions for $p = 3$. Namely, $x = -2, y = 1$ and $x = -1, y = 2$.

Otherwise, note that neither of $b, n$ can be divisible by $3$ without $b, c$ having a common factor of $3$. Hence $b^2 = n^2 = 1 \ (mod \ 3)$ and we have:
$$p = 1 \ (mod \ 3)$$
For example, we have no solutions for $p = 2, 5$, but we have a triple solution for $p = 7$:
$$x= -3, y = 1, z = 2\ \ \text{with} \ f(x) = f(y) = f(z) = -6$$

 

[fresh_42]

We have opened a second part:
https://www.physicsforums.com/threads/math-challenge-march-2020-part-ii.985311/