Timeline for Prove an inequality related to sums of Legendre symbols
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2022 at 2:55 | vote | accept | math110 | ||
| Apr 12, 2022 at 18:34 | history | edited | Will Sawin | CC BY-SA 4.0 |
deleted 36 characters in body
|
| Apr 12, 2022 at 17:11 | history | edited | GH from MO | CC BY-SA 4.0 |
edited body
|
| Apr 12, 2022 at 16:31 | comment | added | Will Sawin | @DavidESpeyer The trick of using convexity to avoid a careful calculation is nice. And yes, nothing except the very last line is special to the Paley graph. | |
| Apr 12, 2022 at 16:26 | comment | added | David E Speyer | Moreover, if all the $A_{ij}$'s associated to edges are equal, then the optimum comes from taking a maximal clique $K$ and giving all vertices the same weight $|K|^{-1}$. | |
| Apr 12, 2022 at 16:25 | comment | added | David E Speyer | Proof: Let $\vec{x}$ achieve the maximum and suppose that $x_i x_j \neq 0$ for $(i,j) \not\in G$. Consider varying $x_i$ and $x_j$ linearly while preserving their sum. Then $\vec{x}^T A \vec{x}$ is convex up on this line segment, so the maximum occurs at one of the two endpoints. We can thus improve the maximum while shrinking the support. $\square$ | |
| Apr 12, 2022 at 16:24 | comment | added | David E Speyer | It looks like this has nothing to do with the Paley graph. Let $G$ be any graph on $n$ vertices and let $A$ be a matrix where $A_{ii} =0$, $A_{ij} >0$ if $(i,j)$ is an edge of $G$ and $A_{ij} < 0$ if $(i,j)$ is not an edge of $G$. Consider the problem of maximizing $\vec{x}^T A \vec{x}$ subject to the constraints $\vec{x} \geq 0$, $\sum x_i = 1$. I claim that the maximum occurs on a clique. (continued) | |
| Apr 12, 2022 at 15:43 | history | edited | Will Sawin | CC BY-SA 4.0 |
added 106 characters in body
|
| Apr 12, 2022 at 14:30 | history | edited | Will Sawin | CC BY-SA 4.0 |
added 649 characters in body
|
| Apr 12, 2022 at 14:19 | comment | added | math110 | @WillSawin,oh,Nice,I have understand,+1 | |
| Apr 12, 2022 at 13:46 | comment | added | Will Sawin | @msexkac This is explained in GH from MO's comment. The eigenvectors are $\begin{pmatrix} e^{ 2\pi i n / p } \\ e^{ 2 \pi i 2 n/ p } \\ \dots \\ e^{ 2\pi i p n /p } \end{pmatrix}$ for $n \in \{1,\dots, p\}$ and the eigenvalue of this eigenvector can be computed to be a Gauss sum if $n \neq p$ or $0$ if $n=p$. The Gauss sums are all either $\sqrt{p}$ or $-\sqrt{p}$, so the largest one is $p$. | |
| Apr 12, 2022 at 13:26 | comment | added | math110 | the largest real eigenvalue of the $p\times p$ matrix with entries $\left(\dfrac{i-j}{p}\right)$ is the Gauss sum $\sqrt{p}$,why? | |
| Apr 12, 2022 at 3:01 | history | edited | GH from MO | CC BY-SA 4.0 |
added 36 characters in body
|
| Apr 12, 2022 at 2:50 | history | edited | GH from MO | CC BY-SA 4.0 |
added 5 characters in body
|
| Apr 12, 2022 at 2:49 | comment | added | GH from MO | Perhaps it is wortwhile to note that the eigenvalues of the $p\times p$ matrix with entries $\left(\frac{i-j}{p}\right)$ are $\pm\sqrt{p}$ with multiplicity $(p-1)/2$, and zero. The eigenvectors are $(e_p(n),e_p(2n),...)^T$ for $n\in\{1,\dotsc,p\}$. | |
| Apr 12, 2022 at 2:18 | history | edited | Will Sawin | CC BY-SA 4.0 |
added 585 characters in body
|
| Apr 12, 2022 at 2:06 | history | answered | Will Sawin | CC BY-SA 4.0 |