Math Challenge - July 2019

[nuuskur]

I think #86 is not sufficient. We still need the other direction: image of a cyclic subspace is an ideal or else there are potential well-definedness problems of the supposed isomorphism of lattices. Right now, we have
$$I \text{ ideal} \implies T^{-1}(I) \text{ cyclic}$$
We'd also need
$$C\text{ cyclic} \implies T(C) \text{ ideal}$$

Spoiler: Problem 6 - finishing touches

Put
$$T : \mathbb F_q^n \to \mathbb F_q[x] / (x^n-1) =:R,\ (a_0,\ldots, a_{n-1}) \mapsto a_0 + \sum _{k=1}^{n-1} a_kx^{k}$$
Let $C \subseteq \mathbb F_q^n$ be cyclic. We show $T(C)$ is an ideal. As $C$ is a subspace and $T$ is compatible with addition, $T(C)$ is a subgroup. Take $r_0 + \sum_{k=1}^{n-1}r_kx^k\in R$ and $a_0 + \sum_{k=1}^{n-1}\in T(C)$. We must show their product is in $T(C)$.
$$\begin{align*}<br /> &\left (r_0 + \sum_{k=1}^{n-1}r_kx^k\right ) \left (a_0 + \sum_{k=1}^{n-1}a_kx^k\right ) \\<br /> =&r_0\left (a_0 + a_1x + a_2x^2 + \ldots + a_{n-1}x^{n-1}\right ) \\<br /> +&r_1\left (a_0 + a_1x + a_2x^2 + \ldots + a_{n-1}x^{n-1} \right )x \\<br /> +&r_2\left (a_0 + a_1x + a_2x^2 + \ldots + a_{n-1}x^{n-1}\right ) x^2 \\<br /> &\vdots \\<br /> +&r_{n-1} \left ( a_0 + a_1x + a_2x^2 + \ldots + a_{n-1}x^{n-1} \right )x^{n-1}.<br /> \end{align*}$$
As $C$ is a subspace, it is closed w.r.t multiplying by $r_k$. We also saw in #86 that multiplying by $x^k$ shifts the coefficients, but $C$ is cyclic, thus closed w.r.t shifting. All of the additives are in $T(C)$, therefore $T(C)$ is an ideal.

 

[member 587159]

I think #86 is not sufficient. We still need the other direction: image of a cyclic subspace is an ideal or else there are potential well-definedness problems of the supposed isomorphism of lattices. Right now, we have
$$I \text{ ideal} \implies T^{-1}(I) \text{ cyclic}$$
We'd also need
$$C\text{ cyclic} \implies T(C) \text{ ideal}$$

Spoiler: Problem 6 - finishing touches

Put
$$T : \mathbb F_q^n \to \mathbb F_q[x] / (x^n-1) =:R,\ (a_0,\ldots, a_{n-1}) \mapsto a_0 + \sum _{k=1}^{n-1} a_kx^{k}$$
Let $C \subseteq \mathbb F_q^n$ be cyclic. We show $T(C)$ is an ideal. As $C$ is a subspace and $T$ is compatible with addition, $T(C)$ is a subgroup. Take $r_0 + \sum_{k=1}^{n-1}r_kx^k\in R$ and $a_0 + \sum_{k=1}^{n-1}\in T(C)$. We must show their product is in $T(C)$.
$$\begin{align*}<br /> &\left (r_0 + \sum_{k=1}^{n-1}r_kx^k\right ) \left (a_0 + \sum_{k=1}^{n-1}a_kx^k\right ) \\<br /> =&r_0\left (a_0 + a_1x + a_2x^2 + \ldots + a_{n-1}x^{n-1}\right ) \\<br /> +&r_1\left (a_0 + a_1x + a_2x^2 + \ldots + a_{n-1}x^{n-1} \right )x \\<br /> +&r_2\left (a_0 + a_1x + a_2x^2 + \ldots + a_{n-1}x^{n-1}\right ) x^2 \\<br /> &\vdots \\<br /> +&r_{n-1} \left ( a_0 + a_1x + a_2x^2 + \ldots + a_{n-1}x^{n-1} \right )x^{n-1}.<br /> \end{align*}$$
As $C$ is a subspace, it is closed w.r.t multiplying by $r_k$. We also saw in #86 that multiplying by $x^k$ shifts the coefficients, but $C$ is cyclic, thus closed w.r.t shifting. All of the additives are in $T(C)$, therefore $T(C)$ is an ideal.

Your solution seems fine to me now. Well done!

 

[Not anonymous]

Solution to problem 13.

Spoiler

Proof by contradiction. Suppose all the 3 products, $u(1 - v), v (1 - w) and w(1 - u)$ are greater than $1/4$. Then it follows that:

$u(1 - v) > 1/4 \Rightarrow u > 1/4(1-v) \Rightarrow (1 - u) < 1 - 1/4(1-v)\;\;\; \mathcal (Eq. 1)$

$v(1 - w) > 1/4 \Rightarrow v > 1/4(1-w) \Rightarrow (1- w) > 1/4v \Rightarrow w < 1 - 1/4v\;\;\; \mathcal (Eq. 2)$

From (Eq. 1) and (Eq. 2), it follows that
$w(1-u) < (1 - 1/4(1-v)) \cdot (1 - 1/4v) = ((3 - 4v) / 4(1 - v)) \cdot (4v - 1) / 4v \\ = (3 - 4v) (4v - 1) / 16v(1-v) = (12v - 3 - 16v^2 + 4v) / 16v(1-v) \\ = (16v - 16v^2 - 3) / 16v(1-v) = (16v(1-v) - 3) / 16v(1 - v) \\ = 1 - 3 / 16v(1-v)$

It it easy to see that for RHS to have maximum value, the denominator of the subtracted value should be maximal. It is trivial to show that $v(1-v)$ reaches maximum when $v\; =\; 0.5$ and therefore the maximum value of RHS would be $1 - 3 / (16 \times 0.5 \times (1 - 0.5)) = 1/4$. It follows that $w(1 - u) < 1/4$, disproving the initial assumption that all 3 products could be greater than $1/4$

 

[mfb]

You can save some steps in that proof:

Spoiler

Assume there are u,v,w such that all three expressions are larger than 1/4. Then the product of the three expressions must be larger than 1/4³ = 1/64.
That product is u(1-u)v(1-v)w(1-w). All factors are positive, to find its maximum we can maximize u(1-u), v(1-v) and w(1-w) individually. The maximum is 1/4 each, the product is 1/64, contradiction.

 

[nuuskur]

I gave my take on 13 in #42. Relies on how I like to prove statements of the form $A_1\lor A_2\lor \ldots \lor A_n$. Equivalently, one can prove
$$\neg A_1\land \ldots\land \neg A_{n-1} \implies A_n.$$

 

[fresh_42]

My proof uses $u(1-u)=\frac{1}{4}-(u-\frac{1}{2})^2< \frac{1}{4}$ since squares are positive.

 

[Pi-is-3]

My proof uses $u(1-u)=\frac{1}{4}-(u-\frac{1}{2})^2< \frac{1}{4}$ since squares are positive.

Wow. That is the simplest proof for that question!

 

[mfb]

My proof uses $u(1-u)=\frac{1}{4}-(u-\frac{1}{2})^2< \frac{1}{4}$ since squares are positive.

$\leq$ as u=1/2 is possible - squares can be zero. I didn't go into detail with that part as it is very easy to show and a well-known result, too.

 

[Pi-is-3]

$\leq$ as u=1/2 is possible - squares can be zero. I didn't go into detail with that part as it is very easy to show and a well-known result, too.

I think that's just a typo.

 

[fresh_42]

$\leq$ as u=1/2 is possible - squares can be zero. I didn't go into detail with that part as it is very easy to show and a well-known result, too.

Hey, I was lazy: "<" is on the keyboard $"\leq"$ is not. These details are trivial and left to the reader ;-)

 

[nuuskur]

Hey, I was lazy: "<" is on the keyboard $"\leq"$ is not. These details are trivial and left to the reader ;-)

That reminds me of a statistics course lecture. The lector said something like "..and since $f$ is injective, it is invertible..". Similarly, in algebra, saying something is a subgroup of $G$ is to be read as "is an isomorphic copy of a subgroup of $G$".

 

[fresh_42]

That reminds me of a statistics course lecture. The lector said something like "..and since $f$ is injective, it is invertible..". Similarly, in algebra, saying something is a subgroup of $G$ is to be read as "is an isomorphic copy of a subgroup of $G$".

or omitting "almost everywhere" in measure theory.

I have also seen isomorphic for monomorphic (here, not in books), which I really dislike.