Challenge Math Challenge - March 2020

[suremarc]

@suremarc Your solution is good, but you could elaborate on why $F(\mathbb{R}^n)$ is open?

Keep in mind that a function that is a homeomorphism onto its image does not always have open image (e.g. embed $\mathbb{R}\hookrightarrow\mathbb{R}^2$ in the obvious way).

D’oh. This turned out to be more complicated than I thought. However, when $\mathbb{R}^n$ is the domain and codomain, one can apply invariance of domain to show that the image is open.

In both your problem and @fresh_42’s, I wanted to avoid assumptions based on Euclidean space. I guess my nature compels me to formulate things as generally as possible. However, it seems that in this case the solution depends on a nontrivial property of $\mathbb{R}^n$. I have much to learn when it comes to topology...

 

[fresh_42]

This problem took me 3 days, so hopefully I didn't mess up

I expect that there is almost certainly a much easier way to do this problem, which I could not find. But I did manage to obtain a much better bound, so I suppose there's that.

Spoiler: Solution

We use the following result from https://www.researchgate.net/publication/318418316_The_Non-Commutative_Binomial_Theorem: in any unital Banach algebra, we have $$e^{X+Y}=e^Xe^Y+\left(\sum_{n=0}^\infty\frac{D_n(Y,X)}{n!}\right)e^Y$$ where $$D_{n+1}(Y,X)=[Y,X^n+D_n(Y,X)]+X\cdot D_n(Y,X)$$ is defined by a recurrence relation, with $D_0(Y,X)=D_1(Y,X)=0$. From this it is clear that $D_2(Y,X)=[Y,X]$.

Assume that $X,Y\in\mathcal{A}$ where $\mathcal{A}$ is a unital Banach algebra. Our strategy is as follows: factor the non-commuting part as $\gamma([Y,X])$, where $\gamma$ is some element of the operator algebra $B(\mathcal{A})$ dependent on $X$ and $Y$, then obtain bounds on its operator norm. Firstly, let us work in the enveloping algebra of $\mathcal{A}$. Let us denote $\mathrm{ad}_X=L_X-R_X$. We can rewrite $D_n$ in the following manner: $$D_{n+1}(Y,X)=[Y,X^n]+(L_X+\mathrm{ad}_Y)(D_n(Y,X)).$$ Our goal is to rewrite $D_n$ as a linear combination of previous elements in the sequence, for reasons that will become clear. Observe that $[Y,X^n]=[Y,X^{n-1}]X+X^{n-1}[Y,X]$. Since $D_{n+1}-(L_X+\mathrm{ad}_Y)D_n=[Y,X^n]$, we have $$[Y,X^n]=[Y,X^{n-1}]X+X^{n-1}[Y,X]=\left(D_n-(L_X+\mathrm{ad}_Y)(D_{n-1})\right)X+X^{n-1}[Y,X].$$ This implies that we can rewrite $D_n$ in the following manner: $$D_{n+2}=(D_{n+1}-(L_X+\mathrm{ad}_Y)(D_{n}))X+X^n[Y,X]+(L_X+\mathrm{ad}_Y)(D_{n+1})\\=X^n[Y,X]+(L_X+R_X+\mathrm{ad}_Y)(D_{n+1})-R_X(L_X+\mathrm{ad}_Y)(D_n).$$ Now, suppose that there exists $\Gamma_n\in B(\mathcal{A})$ for $n<k$ such that $\Gamma_n([Y,X])=D_n(Y,X)$. Then, provided that $k\geq 2$, one can find $\Gamma_k$ such that $\Gamma_k([Y,X])=D_k(Y,X)$, using the second-order equation for $D_n$: $$\Gamma_k=L_{X^{k-2}}+(L_X+R_X+\mathrm{ad}_Y)\Gamma_{k-1}-R_X(L_X+\mathrm{ad}_Y)\Gamma_k.$$ Letting $\Gamma_0=\Gamma_1=0$, we have $k=2$ and the formula holds for all $\Gamma_n$ by induction. (In particular, $\Gamma_2=\mathrm{id_{\mathcal{A}}}$.) Now let $\gamma=\sum_{n=0}^\infty\frac{\Gamma_n}{n!}$ and we have the formula $e^{X+Y}-e^Xe^Y = \gamma([Y,X])\cdot e^Y$.

Now we obtain bounds on the operator norm of $\gamma$, for $\|e^{X+Y}-e^Xe^Y\|\leq\|\gamma\|_{\mathrm{op}}\,\|[Y,X]\|\,\|e^Y\|$. First note that
$$\|\gamma\|_{\mathrm{op}}\leq\sum_{n=0}^\infty\frac{\|\Gamma_n\|_{\mathrm{op}}}{n!}$$ by subadditivity. From the defining recurrence relation of $\Gamma_n$, we have the following inequality: $$\|\Gamma_{n+2}\|\leq\|L_X\|^n+(\|L_X\|+\|R_X\|+\|\mathrm{ad}_Y\|\,\|\Gamma_{n+1}\|+\|R_X\|(\|L_X\|+\|\mathrm{ad}_Y\|)\,\|\Gamma_n\|$$ by subadditivity and submultiplicativity of the operator norm. We can make substitutions based on the fact that $\|L_X\|_{\mathrm{op}},\|R_X\|_{\mathrm{op}}\leq\|X\|_{\mathcal{A}}$, implying that $\|\mathrm{ad}_Y\|_{\mathrm{op}}\leq 2\|Y\|_{\mathcal{A}}$. Suppose $\|X\|,\|Y\|\leq C$. Then we have the inequality $$\|\Gamma_{n+2}\|\leq C^n+4C\|\Gamma_{n+1}\|+3C^2\|\Gamma_n\|.$$ Roughly, this suggests that $\|\Gamma_n\|=O(C^{n-2})$ when n is held constant, which we will now make more precise. Let $$a_{n+2}=1+4a_{n+1}+3a_n;\quad a_0=a_1=0.$$ If we have $a_n\geq\|\Gamma_n\|C^{n-2}$ for $n<k$, then one has $$\|\Gamma_k\|\leq C^{k-2}+4C\|\Gamma_{k-1}\|+3C^2\|\Gamma_{k-2}\|\\\leq C^k+4C\cdot C^{k-3}a_{k-1}+3C^2\cdot C^{k-4}a_{k-2}\\=C^{k-2}(1+4a_{k-1}+3a_{k-2})=C^{k-2}a_k$$ which is valid, provided that $k\geq 4$. Observing that the inequality holds for $\|\Gamma_2\|=1$ and $\|\Gamma_3\|\leq 5C$, the inequality holds for all $n\in\mathbb{N}$ by induction.

We now return to the operator $\gamma$: applying the inequality for $\|\gamma\|$ in terms of $\Gamma_n$, we have that $$\|\gamma\|\leq\sum_{n=2}^\infty\frac{C^{n-2}a_n}{n!}$$ The right-hand side is equivalent to $f(C)/C^2$, where $f$ is the unique solution to the differential equation $f''(t)=e^t+4f'(t)+3f(t)$ with $f(0)=0, f'(0)=0$. It can be written as $$f(t)=\frac{1}{84}\left((7-\sqrt{7})e^{(2+\sqrt{7})t}+(7+\sqrt{7})e^{(2-\sqrt{7})t}-14e^t\right).$$ We now have the bound $$\|e^{X+Y}-e^Xe^Y\|\leq\frac{f(C)}{C^2}\|[Y,X]\|\,\|e^Y\|\\\leq\frac{f(C)}{C^2}\|[Y,X]\|e^{\|Y\|}\\\leq\frac{f(C)}{C^2}e^C\|[Y,X]\|.$$ In the case that $\|X\|,\|Y\|\leq 1$, one let's $C\rightarrow 1$: $$\|e^{X+Y}-e^Xe^Y\|\leq f(1)e\|[Y,X]\|\approx 5.01e\|[Y,X]\|\leq 6e^2\|[Y,X]\|.$$ Thus, we have improved significantly on the original inequality.

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*}

 

[suremarc]

You must have nightmares with BCH!

I apologize, but I’m not sure what you mean by this Applying the BCH formula was my first instinct, but I didn’t know enough about the higher-order terms to extract anything useful. So instead I found that paper on the so-called “non-commutative binomial theorem” which helped me get a foothold on the problem.

 

[Adesh]

@Adesh You argue that for $x_2$ to be rational, that $\sqrt{8-3x_1^2}$ must be rational, so $8-3x_1^2$ must be a perfect square. However, this only means that $8-3x_1^2$ is the square of a rational, not necessarily of an integer, so you can't conclude that it has to be $4$ or $1$.

@Not anonymous gave a proof with the same idea (quadratic formula) in post 47 you could look at.

I have used Rolle’s Theorem for proving it.

Spoiler

Let’s assume we draw the graph of $f(x) = x^3 -2x$ on the coordinate system whose x and y axes consist of only rational numbers (well that’s what we are given) .

If in an interval $\left [ a,b \right]$ we have a condition $$ f(a) = f(b)$$ then according to Rolle’s Theorem there exists a $c \in \left(a , b \right)$ such that $$ f’(c) = 0 $$.

Well, let’s assume that there exists such a $c$ then, $$ f’(c) =0 \\
3c^2 -2 =0 \\
c = \sqrt {
\frac{ 2}{3} } $$ But this $c$ doesn’t belong to $\left ( a,b\right)$, because this $c$ is irrational and all the point between $a$ and $b$ is rational.

Therefore, when only rational inputs are allowed we cannot get $f(a) = f(b)$ for distinct $a$ and $b$ and hence $f$ is injective.

 

[Infrared]

@suremarc Great, invariance of domain certainly does the trick. I'm not sure if there's an easy, direct way that avoids using some topology.

@Adesh Nice solution! I hadn't thought of using Rolle's theorem like that. [Edit: As @archaic noted, the argument isn't sound]

 

[archaic]

I have used Rolle’s Theorem for proving it.

Spoiler

Let’s assume we draw the graph of $f(x) = x^3 -2x$ on the coordinate system whose x and y axes consist of only rational numbers (well that’s what we are given) .

If in an interval $\left [ a,b \right]$ we have a condition $$ f(a) = f(b)$$ then according to Rolle’s Theorem there exists a $c \in \left(a , b \right)$ such that $$ f’(c) = 0 $$.

Well, let’s assume that there exists such a $c$ then, $$ f’(c) =0 \\
3c^2 -2 =0 \\
c = \sqrt {
\frac{ 2}{3} } $$ But this $c$ doesn’t belong to $\left ( a,b\right)$, because this $c$ is irrational and all the point between $a$ and $b$ is rational.

Therefore, when only rational inputs are allowed we cannot get $f(a) = f(b)$ for distinct $a$ and $b$ and hence $f$ is injective.

I don't see why the nature of $c$ influences that of $a$ and $b$. For $f(x)=(x-1)(x-2)(x-3)$, we have $f'(x)=0$ for $x=\frac{6\pm\sqrt 3}{3}$, an irrational with $\frac{6-\sqrt 3}{3}\in(1,\,2)$ but not in the rational interval $(1,\,2)$ and $f(1)=f(2)$.

 

[Infrared]

@archaic Good catch! @Adesh there is no reason why $c$ has to be rational, so I don't think the contradiction works.

 

[Adesh]

@archaic Good catch! @Adesh there is no reason why $c$ has to be rational, so I don't think the contradiction works.

It's because if x-axis consists of only rational numbers (which is our domain), and if our function ever makes a u-turn then at some point on x-axis it has to have a derivative of zero.

If c doesn't lie between $a$ and $b$ that means c doesn't lie on the x-axis and hence function doesn't take a u-turn.

I'm always available to give all kinds of justifications.

 

[Infrared]

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.

 

[Adesh]

I don't see why the nature of $c$ influences that of $a$ and $b$. For $f(x)=(x-1)(x-2)(x-3)$, we have $f'(x)=0$ for $x=\frac{6\pm\sqrt 3}{3}$, an irrational with $\frac{6-\sqrt 3}{3}\in(1,\,2)$ but not in the rational interval $(1,\,2)$ and $f(1)=f(2)$.

Because $c$ doesn't belong to the domain of $f$ but $a$ and $b$ do.

Let me explain it with a similar example, I'm going to quote from SL Loney's The Elements of Coordinate Geometry, article 153, page 121:

Point of intersection , in general, of the straight line , $$ y = mx +c$$ with the circle $$ x^2 + y ^2 =a^2$$
The coordinates of points in which the straight line meets the circle satisfy both the equations, therefore
$$ x^2 +( mx+c)^2 =a \\
x^2 (1+m^2) +2mxc +c^2-a^2=0 $$
The roots of this equation may be real, coincident or imaginary according as $$ (2mc)^2 -4(1+m^2) (c^2-a^2) ~ \textrm{is positive, zero or negative, i.e., according as } \\
a^2 (1+m^2) -c^2 ~\textrm{is positive, zero or negative}$$
...
When $c^2$ is greater than $a^2(1+m^2)$, the line doesn't meet the circle at all, or rather this is better expressed by saying that it meets the circle in imaginary points

 

[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/