Math Challenge - February 2020

  • Challenge
  • Thread starter fresh_42
  • Start date
  • Featured
  • #76
137
62
The idea for the proof is as follows. Basically for chosen functional ##F##, we want to find a decomposition of vectors of ##\mathcal{H}## to the ones belonging to its kernel, and the ones belonging to the orthogonal complement of the kernel, where orthogonal complement is defined with respect to the bilinear form ##\beta##. This will allow us to make a decomposition of a vector such that actions of the bilinear form and functional on it coincide, so we find the relation we need. We construct the proof, by first inspecting the property of orthogonal complement.

I will assume here that ##\beta(x,x) = 0## is equivalent to ##x=0##, since that wasn't mentioned, but if we take that all vectors have non-zero norm, we exclude the zero vector(cause the form is bilinear) from the space, which shouldn't happen.

Denote ##K = \ker F## which is a subset of ##\mathcal{H}##(a closed subset, by continuity of ##F##), we assert that ##K^\perp## is one-dimensional(if we exclude the trivial case where kernel would take up the whole space, for which choice ##f^\dagger=0## would suffice). Suppose that it isn't, that there are two independent non-zero vectors ##v_1## and ##v_2## in ##\mathcal{H}##, that belong to ##K^\perp##. Then we have that ##F(v_1)v_2 - F(v_2)v_1## is a non-zero vector from ##K^\perp##, but by linearity of ##F## we have that
$$F(F(v_1)v_2-F(v_2)v_1) = 0$$
which is a contradiction as it would indicate ##F(v_1)v_2 - F(v_2)v_1 \in K##. We can extend this argument to any number of dimensions.
Assume ##K^\perp## is spanned by ##n## vectors. Then we create sum of form:
$$v=\sum_i a_i F(y_1)F(y_2)\dots y_i F(y_{i+1})\dots F(y_n) $$
such that ##\sum_i a_i=0##.
Then ##F(v)=0##, similar to above so its a contradiction.
So ##K^\perp## is one-dimensional.
Let's find a vector ##w\in K^\perp## such that ##F(w) = \beta(w,w)##.
Choose:
$$w= \frac{yF(y)}{\beta(y,y)}$$
for some non-zero ##y\in K^\perp##. By substitution we see that it satisfies the relation above that we wanted to impose. We can span ##K^\perp## with ##w##.
That means that any vector from ##\mathcal{H}## can be decomposed in the form ##v = u + kw##, where ##k## is a scalar, ##u\in K## and ##w \in K^\perp##. It follows that:
$$F(x) = kF(w) = k\beta(w,w) = \beta(w,u + kw) = \beta(w,x)$$
where we used ##\beta(u,w)=0## - the orthogonal complement definition, and ##F(u) = 0## cause ##u\in K##. Therefore we constructed ##w\in\mathcal{H}## such that ##F(x) = \beta(w,x)##, so in our formula ##w=f^\dagger##.

Let's prove uniqueness. Suppose there are ##f_1^\dagger## and ##f_2^\dagger## that both satisfy the identity ##F(x) = \beta(f,x)## for all ##x\in\mathcal{H}##.
Then, take ##x = f_1^\dagger - f_2^\dagger##. It follows that:
$$F(x) = \beta(f_1^\dagger, f_1^\dagger-f_2^\dagger)$$
but also:
$$F(x) = \beta(f_2^\dagger,f_1^\dagger-f_2^\dagger)$$
Subtracting the identities above we find:
$$\beta(f_1^\dagger - f_2^\dagger, f_1^\dagger-f_2^\dagger) = 0 \Rightarrow f_1^\dagger = f_2^\dagger.$$
The uniqueness is thus proved.
 
Last edited:
  • #77
321
75
What I ask for, is an approach / solution using some sort of limits. I say "using calculus" in the wording of the question, which is not clear enough but if I make it totally clear, I'll give the way of the solution ;)
Maybe like this?
$$\begin{align*}
\int_a^b\,f(x)dx&=\lim_{n\to\infty}\sum_{k=0}^{n}\,f\left(a+k\frac{b-a}{n}\right)\frac{b-a}{n}\\
&=\lim_{n\to\infty}\sum_{k=0}^{n}\,f\left((a+d)-d+k\frac{(b+d)-(a+d)}{n}\right)\frac{(b+d)-(a+d)}{n}\\
&=\int_{a+d}^{b+d}f(x-d)dx
\end{align*}$$
 
Last edited:
  • #78
12,533
8,948
The idea for the proof is as follows. Basically for chosen functional ##F##, we want to find a decomposition of vectors of ##\mathcal{H}## to the ones belonging to its kernel, and the ones belonging to the orthogonal complement of the kernel, where orthogonal complement is defined with respect to the bilinear form ##\beta##. This will allow us to make a decomposition of a vector such that actions of the bilinear form and functional on it coincide, so we find the relation we need. We construct the proof, by first inspecting the property of orthogonal complement.

I will assume here that ##\beta(x,x) = 0## is equivalent to ##x=0##, since that wasn't mentioned, but if we take that all vectors have non-zero norm, we exclude the zero vector(cause the form is bilinear) from the space, which shouldn't happen.

Denote ##K = \ker F## which is a subset of ##\mathcal{H}##(a closed subset, by continuity of ##F##), we assert that ##K^\perp## is one-dimensional(if we exclude the trivial case where kernel would take up the whole space, for which choice ##f^\dagger=0## would suffice). Suppose that it isn't, that there are two independent non-zero vectors ##v_1## and ##v_2## in ##\mathcal{H}##, that belong to ##K^\perp##. Then we have that ##F(v_1)v_2 - F(v_2)v_1## is a non-zero vector from ##K^\perp##, but by linearity of ##F## we have that
$$F(F(v_1)v_2-F(v_2)v_1) = 0$$
which is a contradiction as it would indicate ##F(v_1)v_2 - F(v_2)v_1 \in K##. We can extend this argument to any number of dimensions.
Assume ##K^\perp## is spanned by ##n## vectors. Then we create sum of form:
$$v=\sum_i a_i F(y_1)F(y_2)\dots y_i F(y_{i+1})\dots F(y_n) $$
such that ##\sum_i a_i=0##.
Then ##F(v)=0##, similar to above so its a contradiction.
So##K^\perp## is one-dimensional.
Let's find a vector ##w\in K^\perp## such that ##F(w) = \beta(w,w)##.
Choose:
$$w= \frac{yF(y)}{\beta(y,y)}$$
for some non-zero ##y\in K^\perp##. By substitution we see that it satisfies the relation above that we wanted to impose. We can span ##K^\perp## with ##w##.
That means that any vector from ##\mathcal{H}## can be decomposed in the form ##v = u + kw##, where ##k## is a scalar, ##u\in K## and ##w \in K^\perp##. It follows that:
$$F(x) = kF(w) = k\beta(w,w) = \beta(w,u + kw) = \beta(w,x)$$
where we used ##\beta(u,w)=0## - the orthogonal complement definition, and ##F(u) = 0## cause ##u\in K##. Therefore we constructed ##w\in\mathcal{H}## such that ##F(x) = \beta(w,x)##, so in our formula ##w=f^\dagger##.

Let's prove uniqueness. Suppose there are ##f_1^\dagger## and ##f_2^\dagger## that both satisfy the identity ##F(x) = \beta(f,x)## for all ##x\in\mathcal{H}##.
Then, take ##x = f_1^\dagger - f_2^\dagger##. It follows that:
$$F(x) = \beta(f_1^\dagger, f_1^\dagger-f_2^\dagger)$$
but also:
$$F(x) = \beta(f_2^\dagger,f_1^\dagger-f_2^\dagger)$$
Subtracting the identities above we find:
$$\beta(f_1^\dagger - f_2^\dagger, f_1^\dagger-f_2^\dagger) = 0 \Rightarrow f_1^\dagger = f_2^\dagger.$$
The uniqueness is thus proved.
At first sight it looks as if you had proven Riesz' representation theorem. However, the task is a different one. We want to know its generalization to any continuous bilinear form which is bounded on the diagonal from below, but which doesn't necessarily define orthogonality. Riesz' representation theorem is useful for the proof, but not equivalent to the statement.
 
  • #79
11. b.) In how many different ways can eight queens be placed on a chessboard, such that no queen threatens another? Two solutions are not different, if they can be achieved by a rotation or by mirroring of the board. (For this part there is no proof required.)
Is the answer 17? I consider an arrangement to be "different" or "unique" if it cannot be obtained as a rotation (by 90, 180 or 270 degrees) or as a mirror image (reflect across horizontal or vertical center line of chessboard) of any other arrangement in the unique set. The following are 17 unique arrangements I get:
  1. [1, 5, 8, 6, 3, 7, 2, 4]
  2. [1, 6, 8, 3, 7, 4, 2, 5]
  3. [1, 7, 4, 6, 8, 2, 5, 3]
  4. [1, 7, 5, 8, 2, 4, 6, 3]
  5. [2, 4, 6, 8, 3, 1, 7, 5]
  6. [2, 5, 7, 1, 3, 8, 6, 4]
  7. [2, 5, 7, 4, 1, 8, 6, 3]
  8. [2, 6, 1, 7, 4, 8, 3, 5]
  9. [2, 6, 8, 3, 1, 4, 7, 5]
  10. [2, 7, 3, 6, 8, 5, 1, 4]
  11. [2, 7, 5, 8, 1, 4, 6, 3]
  12. [3, 1, 7, 5, 8, 2, 4, 6]
  13. [3, 5, 2, 8, 1, 7, 4, 6]
  14. [3, 5, 8, 4, 1, 7, 2, 6]
  15. [3, 6, 2, 5, 8, 1, 7, 4]
  16. [3, 6, 2, 7, 1, 4, 8, 5]
  17. [3, 6, 2, 7, 5, 1, 8, 4]
Each array or list above is to be interpreted as denoting an arrangement with each element in the list denoting the column number (occupied on the chessboard) of the queen placed in the row number corresponding to the index of that element of that list. So for example, arrangement [3, 6, 2, 7, 5, 1, 8, 4] means that in row 1 of the chessboard, the queen is placed in column 3, in row 2, the queen is in column 6 and so on till in row 8, the queen is in column 4.

If the answer is correct, I can share the script I wrote to find the solution, if that will help.
 
  • #80
12,533
8,948
17 is too many, but reflections along the diagonals are considered equal. Do you have the number without equivalence, i.e. how many possibilities at all?

Remember that I only need the numbers, regardless how you found them.
 
  • #81
17 is too many, but reflections along the diagonals are considered equal. Do you have the number without equivalence, i.e. how many possibilities at all?

Remember that I only need the numbers, regardless how you found them.
When not considering rotations and mirror images as being equivalent, I got 92 different ways to place 8 queens on 8x8 chessboard such that no 2 queens attack each other. I had not considered the possibility of reflection along diagonals in the solution I had posted.
 
  • #82
12,533
8,948
92 is correct. Fundamental solutions are less than 17.
 
  • #83
92 is correct. Fundamental solutions are less than 17.
Thanks. Will look at the arrangements from the earlier solution again after sometime and find duplicates arising from diagonal reflections
 
  • #84
92 is correct. Fundamental solutions are less than 17.
Is the answer 12? The following are the unique arrangements when diagonal reflections also to be treated as non-unique.
  1. [1, 5, 8, 6, 3, 7, 2, 4]
  2. [1, 6, 8, 3, 7, 4, 2, 5]
  3. [2, 4, 6, 8, 3, 1, 7, 5]
  4. [2, 5, 7, 1, 3, 8, 6, 4]
  5. [2, 5, 7, 4, 1, 8, 6, 3]
  6. [2, 6, 1, 7, 4, 8, 3, 5]
  7. [2, 6, 8, 3, 1, 4, 7, 5]
  8. [2, 7, 3, 6, 8, 5, 1, 4]
  9. [2, 7, 5, 8, 1, 4, 6, 3]
  10. [3, 5, 2, 8, 1, 7, 4, 6]
  11. [3, 5, 8, 4, 1, 7, 2, 6]
  12. [3, 6, 2, 5, 8, 1, 7, 4]
The arrangements in my earlier solution that are now considered non-unique because they are diagonal reflections of some other arrangement in the final solution are:
[1, 7, 4, 6, 8, 2, 5, 3]
[1, 7, 5, 8, 2, 4, 6, 3]
[3, 1, 7, 5, 8, 2, 4, 6]
[3, 6, 2, 7, 1, 4, 8, 5]
[3, 6, 2, 7, 5, 1, 8, 4]
 
  • #85
12,533
8,948
Is the answer 12? The following are the unique arrangements when diagonal reflections also to be treated as non-unique.
  1. [1, 5, 8, 6, 3, 7, 2, 4]
  2. [1, 6, 8, 3, 7, 4, 2, 5]
  3. [2, 4, 6, 8, 3, 1, 7, 5]
  4. [2, 5, 7, 1, 3, 8, 6, 4]
  5. [2, 5, 7, 4, 1, 8, 6, 3]
  6. [2, 6, 1, 7, 4, 8, 3, 5]
  7. [2, 6, 8, 3, 1, 4, 7, 5]
  8. [2, 7, 3, 6, 8, 5, 1, 4]
  9. [2, 7, 5, 8, 1, 4, 6, 3]
  10. [3, 5, 2, 8, 1, 7, 4, 6]
  11. [3, 5, 8, 4, 1, 7, 2, 6]
  12. [3, 6, 2, 5, 8, 1, 7, 4]
The arrangements in my earlier solution that are now considered non-unique because they are diagonal reflections of some other arrangement in the final solution are:
[1, 7, 4, 6, 8, 2, 5, 3]
[1, 7, 5, 8, 2, 4, 6, 3]
[3, 1, 7, 5, 8, 2, 4, 6]
[3, 6, 2, 7, 1, 4, 8, 5]
[3, 6, 2, 7, 5, 1, 8, 4]
Very good!
 
  • #86
18
1
11. Answer the following questions:
a.) How many knights can you place on a ##n\times m## chessboard such that no two attack each other?
There are three cases. ##r## is the required number.
CASE 1: When any of ##m## & ##n## ##=1##
##r=n/m##
(##r=n## for ##m=1## and vice versa)
CASE 2: When any of ##m## & ##n## ##=2##
(let ##q=## number equal to 2 & ##p=## other number)
1. ##p=4x+0##
##r=\frac{pq}2##
2. ##p=##else
##r=(\lfloor\frac p2\rfloor+1)\times q##
CASE 3: When both ##m## & ##n## ##\gt2##
##r=\lceil\frac{mn}2\rceil##
 
  • #87
12,533
8,948
There are three cases. ##r## is the required number.
CASE 1: When any of ##m## & ##n## ##=1##
##r=n/m##
(##r=n## for ##m=1## and vice versa)
CASE 2: When any of ##m## & ##n## ##=2##
(let ##q=## number equal to 2 & ##p=## other number)
1. ##p=4x+0##
##r=\frac{pq}2##
2. ##p=##else
##r=(\lfloor\frac p2\rfloor+1)\times q##
CASE 3: When both ##m## & ##n## ##\gt2##
##r=\lceil\frac{mn}2\rceil##
Let me sort this out. ##r## be the number of knights on an ##n \times m## board.

You already correctly had the cases ##m=1## in which we get ##r=n## and ##m>2## with ##r=\lceil\frac{mn}2\rceil##. Now only ##m=2## was left to do.

If ##m=2## and ##n=4k## then you say ##r=n##, since ##m=q=2## and thus ##q/2=1\, , \,p=r=n.##
This is correct.

If ##m=2## and ##n=4k+s## with ##s=1,2,3## then you get ##r=(\lfloor\frac p2\rfloor+1)\times q## which is in the variables of the problem ##r=(\lfloor\frac n2\rfloor+1)\times 2##.
This is correct, too.

The arrangement in case of two rows is
1581663447288.png
 
  • #88
137
62
In order to calculate the Legendre symbol ##\left(\frac{a}{p}\right)##, we are going to use Euler's criterion:
$$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$$

Observing that ##\lambda_{a,p}## is a permutation, we will decompose it into cycles. We observe that any cycle that is a part of the permutation must be of form: ##(x, ax, a^2x, a^3x,\dots, a^kx)##, where ##k## is the smallest natural number such that ##a^{k+1} \equiv 1 \pmod{p}##, and every number in the cycle is taken modulo ##p##.
Such a number ##k## exists and is smaller than ##p-1##, since we have only ##p-1## distinct elements in ##\mathbb{Z}_p^\times##.
We also observe that all cycles in our permutation must be of same length, because this permutation is induced by left multiplication. That is, if ##k## is the smallest number such that ##a^{k+1} \equiv 1 \pmod{p}##, then there can't be another number ##l## satisfying the same property(because only one of them can be considered 'smallest'), and so the cycle will always be terminated by ##a^kx##, for every ##x##, and fixed ##a##.

We conclude that, if we take ##k## to be the length of a cycle corresponding to number ##a##(cycles then terminate with ##a^{k-1}x##), that there are ##\frac{p-1}{k}## cycles in the permutation ##\lambda_{a,p}##. Every cycle of length ##k## has the signature ##(-1)^{k-1}##. Therefore we have:
$$\text{sgn}(\lambda_{a,p}) = \left((-1)^{k-1}\right)^\frac{p-1}{k}$$
The above expression is equal to ##1## for odd ##k##, and equal to ##(-1)^\frac{p-1}{k}## for even ##k##.
Now also, for even ##k##:
$$a^{\frac{p-1}{2}} = (a^{\frac{k}{2}})^{\frac{p-1}{k}} \equiv (-1)^\frac{p-1}{k} \pmod{p}$$
The last equality above follows because if ##a^k \equiv 1 \pmod{p}## then ##a^\frac{k}{2} \equiv \pm 1 \pmod{p}##. But also we can't have ##a^\frac{k}{2} \equiv 1 \pmod{p}## since ##k## is the smallest positive integer such that this relation holds. Hence it must be ##a^\frac{k}{2} \equiv -1 \pmod{p}##.
For odd ##k##, we have:
$$a^\frac{p-1}{2} = (a^k)^\frac{p-1}{2k} \equiv 1 \pmod{p}$$
Hence we have that, by Euler's criterion we mentioned at the beginning:
$$\left(\frac{a}{p}\right) = \text{sgn}(\lambda_{a,p})$$
QED
 
  • #89
75
29
In order to calculate the Legendre symbol ##\left(\frac{a}{p}\right)##, we are going to use Euler's criterion:
$$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$$

Observing that ##\lambda_{a,p}## is a permutation, we will decompose it into cycles. We observe that any cycle that is a part of the permutation must be of form: ##(x, ax, a^2x, a^3x,\dots, a^kx)##, where ##k## is the smallest natural number such that ##a^{k+1} \equiv 1 \pmod{p}##, and every number in the cycle is taken modulo ##p##.
Such a number ##k## exists and is smaller than ##p-1##, since we have only ##p-1## distinct elements in ##\mathbb{Z}_p^\times##.
We also observe that all cycles in our permutation must be of same length, because this permutation is induced by left multiplication. That is, if ##k## is the smallest number such that ##a^{k+1} \equiv 1 \pmod{p}##, then there can't be another number ##l## satisfying the same property(because only one of them can be considered 'smallest'), and so the cycle will always be terminated by ##a^kx##, for every ##x##, and fixed ##a##.

We conclude that, if we take ##k## to be the length of a cycle corresponding to number ##a##(cycles then terminate with ##a^{k-1}x##), that there are ##\frac{p-1}{k}## cycles in the permutation ##\lambda_{a,p}##. Every cycle of length ##k## has the signature ##(-1)^{k-1}##. Therefore we have:
$$\text{sgn}(\lambda_{a,p}) = \left((-1)^{k-1}\right)^\frac{p-1}{k}$$
The above expression is equal to ##1## for odd ##k##, and equal to ##(-1)^\frac{p-1}{k}## for even ##k##.
Now also, for even ##k##:
$$a^{\frac{p-1}{2}} = (a^{\frac{k}{2}})^{\frac{p-1}{k}} \equiv (-1)^\frac{p-1}{k} \pmod{p}$$
The last equality above follows because if ##a^k \equiv 1 \pmod{p}## then ##a^\frac{k}{2} \equiv \pm 1 \pmod{p}##. But also we can't have ##a^\frac{k}{2} \equiv 1 \pmod{p}## since ##k## is the smallest positive integer such that this relation holds. Hence it must be ##a^\frac{k}{2} \equiv -1 \pmod{p}##.
For odd ##k##, we have:
$$a^\frac{p-1}{2} = (a^k)^\frac{p-1}{2k} \equiv 1 \pmod{p}$$
Hence we have that, by Euler's criterion we mentioned at the beginning:
$$\left(\frac{a}{p}\right) = \text{sgn}(\lambda_{a,p})$$
QED
I was working on this, and took the same approach. Unfortunately, I didn’t realize that k-cycles have the signature ##(-1)^{k-1}##, and not ##(-1)^k##. D’oh!
 
  • #90
12,533
8,948
In order to calculate the Legendre symbol ##\left(\frac{a}{p}\right)##, we are going to use Euler's criterion:
$$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$$

Observing that ##\lambda_{a,p}## is a permutation, we will decompose it into cycles. We observe that any cycle that is a part of the permutation must be of form: ##(x, ax, a^2x, a^3x,\dots, a^kx)##, where ##k## is the smallest natural number such that ##a^{k+1} \equiv 1 \pmod{p}##, and every number in the cycle is taken modulo ##p##.
Such a number ##k## exists and is smaller than ##p-1##, since we have only ##p-1## distinct elements in ##\mathbb{Z}_p^\times##.
We also observe that all cycles in our permutation must be of same length, because this permutation is induced by left multiplication. That is, if ##k## is the smallest number such that ##a^{k+1} \equiv 1 \pmod{p}##, then there can't be another number ##l## satisfying the same property(because only one of them can be considered 'smallest'), and so the cycle will always be terminated by ##a^kx##, for every ##x##, and fixed ##a##.

We conclude that, if we take ##k## to be the length of a cycle corresponding to number ##a##(cycles then terminate with ##a^{k-1}x##), that there are ##\frac{p-1}{k}## cycles in the permutation ##\lambda_{a,p}##. Every cycle of length ##k## has the signature ##(-1)^{k-1}##. Therefore we have:
$$\text{sgn}(\lambda_{a,p}) = \left((-1)^{k-1}\right)^\frac{p-1}{k}$$
The above expression is equal to ##1## for odd ##k##, and equal to ##(-1)^\frac{p-1}{k}## for even ##k##.
Now also, for even ##k##:
$$a^{\frac{p-1}{2}} = (a^{\frac{k}{2}})^{\frac{p-1}{k}} \equiv (-1)^\frac{p-1}{k} \pmod{p}$$
The last equality above follows because if ##a^k \equiv 1 \pmod{p}## then ##a^\frac{k}{2} \equiv \pm 1 \pmod{p}##. But also we can't have ##a^\frac{k}{2} \equiv 1 \pmod{p}## since ##k## is the smallest positive integer such that this relation holds. Hence it must be ##a^\frac{k}{2} \equiv -1 \pmod{p}##.
For odd ##k##, we have:
$$a^\frac{p-1}{2} = (a^k)^\frac{p-1}{2k} \equiv 1 \pmod{p}$$
Hence we have that, by Euler's criterion we mentioned at the beginning:
$$\left(\frac{a}{p}\right) = \text{sgn}(\lambda_{a,p})$$
QED
This result is called Zolotarev's Lemma. You used but haven't explicitly stated that ##k+1=\operatorname{ord}a##. It's a bit easier to read if you start with that definition and the remark that the cycles are disjoint.

Hint for problem 10:
Consider ##B(f)(g)=\beta(f,g)##, and use Riesz representation theorem to establish an isometry ##T## between ##\mathcal{H}^*## and ##\mathcal{H}##. Then apply Banach's fixed-point theorem on the function ##Q(f)=f-\lambda (T(B(f))-T(f))## for a suitable ##\lambda##.
 
  • #91
Infrared
Science Advisor
Gold Member
477
181
I don't know if @fresh_42 didn't want the fact that ##\mathbb{Z}_p^*## is cyclic to be used for problem 9, but the result follows easily from it. If ##a=b^2\in\mathbb{Z}_p^*## is a square, then ##\lambda_a=\lambda_{b}\circ\lambda_{b}## is even. On the other hand, if ##a## is not a square, then it is an odd power of a generator, and hence also a generator. So ##\lambda_a## is a ##(p-1)##-cycle, which is odd.
 
  • #92
12,533
8,948
I don't know if @fresh_42 didn't want the fact that ##\mathbb{Z}_p^*## is cyclic to be used for problem 9, but the result follows easily from it. If ##t## is a generator, and ##a\in\mathbb{Z}_p^*## is a square, then ##a=t^{2k}## for some integer ##k##, so ##\lambda_a=\lambda_{t^k}\circ\lambda_{t^k}## is even. On the other hand, if ##a=t^{2k+1}##, then ##a## is also a generator, so ##\lambda_a## is a ##(p-1)##-cycle and hence odd.
It does no harm to give an elementary proof.
 
  • #93
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
11,770
4,740
Well done @etotheipi. It's a very nice shortcut way for this particular case. However, there is a more general way we can solve problems like this. I won't tell what is it but if anyone else wants to try the problem and come up with a correct solution, he / she'll also get credit.
Can you explain what you mean by problems like this? ##A## is a specific matrix, which is its own inverse. What sort of generalisation are you looking for?
 
  • #94
QuantumQuest
Science Advisor
Insights Author
Gold Member
894
467
Can you explain what you mean by problems like this? ##A## is a specific matrix, which is its own inverse. What sort of generalisation are you looking for?
Well, there is some specific procedure we can follow, a relation coming out of it and then the classic way we treat problems like this.
 
Last edited:
  • #95
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
11,770
4,740
Well, there is some specific procedure we can follow, a relation coming out of it and then the classic way we treat problems like this.
That's all very well, but I have no idea what the question is asking! Problems like what? Perhaps no one has solved it because no one knows what you're driving at.
 
  • #96
22
1
In question 1) is the power of n inside the cosine or outside it?
 
  • #97
QuantumQuest
Science Advisor
Insights Author
Gold Member
894
467
That's all very well, but I have no idea what the question is asking! Problems like what? Perhaps no one has solved it because no one knows what you're driving at.
I'm not saying anything cryptic. When I say problems like this I literally mean it: problems that ask to calculate some power(s) of a matrix. So, in standard curricula for mathematicians, there is a standard way to treat problems like this - the solution given so far in the challenge is absolutely acceptable but there is some more formal way to tackle the whole thing ;)
 
  • #98
Infrared
Science Advisor
Gold Member
477
181
In question 1) is the power of n inside the cosine or outside it?
Outside
 
  • #99
75
29
Since the solution I came up with is relatively simple and ignores @fresh_42’s hint, I feel like I must be completely wrong.

Consider the operator ##\mathrm{B_1}: \mathcal{H}\rightarrow\mathcal{H}## defined by ##\mathrm{B_1}(f)=(\beta(f,\cdot))^*##. The question essentially is asking for a proof that ##\mathrm{B_1}## is a bijection.
Now, ##\beta(f,f)## bounded below implies that ##\mathrm{B_1}## is, too:
$$\beta(f,f)=\langle\mathrm{B_1}f,f\rangle\leq\|\mathrm{B_1}f\|\|f\|$$
by Cauchy-Schwarz;
$$\Rightarrow\|\mathrm{B_1}f\|\|f\|\geq C\|f\|^2\\
\Rightarrow\|\mathrm{B_1}f\|\geq C\|f\|; \|f\|\neq 0.$$
When ##\|f\|=0## the final inequality is trivially true. Additionally, the same can be applied to the map ##\mathrm{B}_2(f)=(\beta(\cdot,f))^*=\mathrm{B}_1^*(f)##.

Now, we use the following fact: a continuous linear map is bounded below iff it is injective with closed range.
This means that ##\mathrm{B_1}## and ##\mathrm{B_2}## are injective with closed range. By the closed range theorem, ##\mathrm{im(B_1)=ker(B_1^*)^\perp=ker(B_2)^\perp}##. But since ##\mathrm{B_2}## is injective, ##\mathrm{ker(B_2)}## is trivial, and so ##\mathrm{im(B_1)}=\mathcal{H}##. So ##\mathrm{B_1}## is injective and surjective, proving the original result.

I tried to use the hint, and was able to apply the fixed point theorem for ##\lambda\in(1,2)##, but didn’t know what to do after that.
 
Last edited:
  • #100
12,533
8,948
Since the solution I came up with is relatively simple and ignores @fresh_42’s hint, I feel like I must be completely wrong.

Consider the operator ##\mathrm{B_1}: \mathcal{H}\rightarrow\mathcal{H}## defined by ##\mathrm{B_1}(f)=(\beta(f,\cdot))^*##. The question essentially is asking for a proof that ##\mathrm{B_1}## is a bijection.
Now, ##\beta(f,f)## bounded below implies that ##\mathrm{B_1}## is, too:
$$\beta(f,f)=\langle\mathrm{B_1}f,f\rangle\leq\|\mathrm{B_1}f\|\|f\|$$
by Cauchy-Schwarz;
$$\Rightarrow\|\mathrm{B_1}f\|\|f\|\geq C\|f\|^2\\
\Rightarrow\|\mathrm{B_1}f\|\geq C\|f\|; \|f\|\neq 0.$$
When ##\|f\|=0## the final inequality is trivially true. Additionally, the same can be applied to the map ##\mathrm{B}_2(f)=(\beta(\cdot,f))^*=\mathrm{B}_1^*(f)##.

Now, we use the following fact: a continuous linear map is bounded below iff it is injective with closed range.
This means that ##\mathrm{B_1}## and ##\mathrm{B_2}## are injective with closed range. By the closed range theorem, ##\mathrm{im(B_1)=ker(B_1^*)^\perp=ker(B_2)^\perp}##. But since ##\mathrm{B_2}## is injective, ##\mathrm{ker(B_2)}## is trivial, and so ##\mathrm{im(B_1)}=\mathcal{H}##. So ##\mathrm{B_1}## is injective and surjective, proving the original result.

I tried to use the hint, and was able to apply the fixed point theorem for ##\lambda\in(1,2)##, but didn’t know what to do after that.
I'm a bit skeptical about your use of duality. E.g. why is ##\operatorname{im}B_1 =\mathcal{H}\,?## Didn't you use ##\mathcal{H}=\left(\mathcal{H}^*\right)^*## with ##\beta## instead of the inner product? In other words: why does ##B_1## land in the space you claim it does? You have only added an asterix.

I know that boundedness and continuity is equivalent. Can you reference the theorem you used to make the range closed, not only dense? I think this is the crucial point. My proof does those things in smaller steps by using Banach to actually define the specific image ##f^\dagger## we are looking for.

The whole theorem is a generalization of Riesz, so we have to be careful with duality, i.e. rigorously separate the inner product and the given bilinear form. The simple notation with an asterix needs a bit of an explanation.
 

Related Threads for: Math Challenge - February 2020

Replies
86
Views
12K
Replies
61
Views
4K
Replies
40
Views
9K
  • Last Post
Replies
20
Views
7K
  • Last Post
Replies
2
Views
2K
Replies
18
Views
1K
Replies
13
Views
1K
Replies
7
Views
2K
Top