# Tag Info

77

Let me answer your question "where do these involution come from" with an elementary geometric explanation. You can skip ahead to the pictures, which are somewhat self-explanatory, I hope. The elements in the the $S$, i.e. triplets $(x,y,z)$ such that $x^2+4yz=p$, can be visualized as a square of side length $x$ together with $4$ rectangles of size $y\... 26 Here is a proof of the conjecture. I will refer several times to the book Cassels: Rational quadratic forms (Academic Press, 1978). 1. Let$p$be a prime such that$p\nmid a$. Using the invertible linear change of variables over$\mathbb{Z}_p$$$x'=ax+bz,\qquad y'=y+(c/a)z,\qquad z'=(1/a)z,$$ we have $$x'y'-(abc)z'^2=axy+byz+czx.$$ Therefore, the quadratic ... 21 The claim is certainly true for$n$sufficiently large, and "sufficiently large" could be specified explicitly with more care. We follow the suggestion of Fedor Petrov, and rely on the results of Brüdern & Fouvry (J. reine angew. Math. 454 (1994), 59-96) and of Heath-Brown & Tolev (J. reine angew. Math. 558 (2003), 159-224). These yield, for any ... 21 This is a well-known fact. A simple proof : setting$y=B^{1/2}x$, we have$\|y\|^2\le y^TB^{-1/2}AB^{-1/2}y$, that is$I_n\le B^{-1/2}AB^{-1/2}$. The eigenvalues of the latter symmetric matrix are thus$\ge1$. Its inverse$B^{1/2}A^{-1}B^{1/2}$has eigenvalues$\le1$, that is$B^{1/2}A^{-1}B^{1/2}\le I_n$. This gives$z^TB^{1/2}A^{-1}B^{1/2}z\le\|z\|^2$. ... 20 Theorem. Let$Q(x_1,\dots,x_k)$be a positive definite integral quadratic form in$k\geq 2$variables. Then the number of integral representations$Q(x_1,\dots,x_k)=n$satisfies $$r_Q(n)\ll_{k,\epsilon}n^{k/2-1+\epsilon}.$$ The implied constant depends only on$k$and$\epsilon$, so it is independent of the actual coefficients of$Q$. Remark. The "Added 1"... 19 Take any square free$1 \neq n \in \mathbb{N}$and recall that$R_n = \mathbb{Z}[\sqrt{n}]$has a multiplicative norm function$N \colon R \to \mathbb{Z}$given by$N(x + y\sqrt{n}) = x^2 -ny^2$so a prime$p$is of the required form iff$p$is a norm in$R_n$(i.e$p$is in the image of$N$). Now take$n$which is not$1$mod$4$(this assures that$R_n$... 19 Also simply for$P(x)=x^4-1$we have $$P\cdot P''+\left(\frac{1}{4} -1 \right)\left(P'\right)^2=-12x^2\leq 0$$ and$P$has imaginary roots. The stronger version is also false. Take$P(x)=x^5-x$which satisfies $$P\cdot P''+\left(\frac{1}{5} -1\right)\left(P'\right)^2=-12x^4-\frac45<0$$ yet it has complex roots. 19 This is an elaboration of Emil Jeřábek's important comment, and contains no original contribution. The OP's problem was examined in depth by Borwein-Choi (1999), and their article is available for free here. I will summarize the content of this article below. Let us consider an integer$n\geq 2$that cannot be written as$ab+bc+ca$with integers$a,b,c\geq ...

18

There is an exact algorithm that needs $n^{O(m)}$ operations (cf. http://arxiv.org/abs/cs/0403008). One cannot expect anything better than that, unless P=NP. Indeed, it is easy to formulate several NP-complete problems as testing solvability of linear equations in 0-1 variables $x_i$, and the latter can be enforced by quadratic equations $x^2_i-x_i=0$.

18

The formula for $r_3(n)$ essentially connects this with a class number of an imaginary quadratic field, or (apart from the $\sqrt{n}$ scaling) with the value of an $L$-function at $1$. So your question may be reformulated as asking how large can $L(1,\chi_{d})$ be as $d$ runs over negative fundamental discriminants ($d$ is essentially $-n$). The ...

18

Let $d$ be a positive fundamental discriminant, $\epsilon_d$ denote the fundamental unit, $h(d)$ the class number, and $\chi_d$ the primitive character associated to the discriminant $d$. The class number formula gives $$\log \epsilon_d = \sqrt{d} L(1,\chi_d)/h(d) \le \sqrt{d} L(1,\chi_d),$$ since the class number $h(d) \ge 1$. Now it is known that $... 17 It is interesting that not only Zagier took this proof from Heath-Brown. Heath-Brown (according to his own words) took this proof from Uspensky. This trick has different applications, see articles of Bykovskii On the arithmetic nature of some identities of the elliptic functions theory and The arithmetic nature of the triple and quintuple product ... 17 Let me restrict to the number of primitive representations $$r_3^\ast(n) = \left|\{(a,b,c)\in {\mathbb Z}^3 :\, a^2+b^2+c^2=n\ \text{and}\ \gcd(a,b,c)=1 \}\right|.$$ Note that$r_3(n)$can be easily expressed from this quantity as $$r_3(n)=\sum_{d^2\mid n}r_3^\ast(n/d^2).$$ Clearly$r_3^*(n)=0$when$n\equiv 0,4,7\pmod{8}$. For the remaining cases, it ... 16 Class field theory promises such a polynomial (more properly, such a number field$H$, since a polynomial generating$H$might have to err on the first few primes, though in our case it turns out there's a polynomial with no exceptional primes). The proof is effective, though the recipe is often hard to carry out. So I attempted an end run by asking this ... 15 Yes. The magic words are "elimination theory" and "resultant". In essence, the system has a solution unless some determinant (the iterated resultant) vanishes. 14 Every prime$p$is represented by at least one of the following quadratic forms:$x^2+y^2$,$x^2+3y^2$,$3x^2-y^2$: if$p=2$or$p\equiv 1\pmod{4}$, then$p$is represented by$x^2+y^2$; if$p=3$or$p\equiv 1\pmod{3}$, then$p$is represented by$x^2+3y^2$; if$p\equiv 11\pmod{12}$, then$p$is represented by$3x^2-y^2$. This follows from Lemma 2.5, ... 13 As$2 = x^2 -2y^2$for$x = 2$and$y=1$we fix an odd prime number$p$, and Claim: There exist integers$x,y$such that$p = x^2 -2y^2$if and only if$p \equiv \pm1 \mod 8$. First if$p = x^2 -2y^2$for some$x,y \in \mathbb{Z}$then observing that the squares mod$8$are$0,1,4$, we conclude that$p$can only be$0,1,2,4,6,7$mod$8$but it is odd so$...

13

Just so you know, one of Dickson's students (A. Oppenheim) finished classifying (indefinite) universal ternaries; the final family is $xy - M z^2.$ Page 161 in Modern Elementary Theory of Numbers. Your conjecture is that $xy-(abc) z^2$ is $SL_3 \mathbb Z$ equivalent to $ayz + b zx + c xy.$ For example, taking $$u = 192x + 50 y + 45 z,$$ $$v = 75 x +... 13 Proof Let R be any matrix. We have the obvious exact sequence$$ 0 \longrightarrow\mathbb{R}^N \xrightarrow[\left(\begin{matrix} I \\ R \end{matrix}\right)]{} \mathbb{R}^N \oplus \mathbb{R}^N \xrightarrow[\left(\begin{matrix} I & -R^{-1} \end{matrix}\right)]{} \mathbb{R}^N \longrightarrow 0 $$This contains as a subsequence$$ 0 \longrightarrow\...

12

The following recent paper: "An exact duality theory for semidefinite programming based on sums of squares" by I. Klep, and M. Schweighofer (both are on MO I think) addresses exactly your question: When is there a $\lambda \in \mathbb{R}^m$ such that $\sum_i \lambda_iA_i \succeq 0$. If you want something simpler, then the following Lemma, cf. L.Lovasz ...

12

It seems that inverse fails in general. In terms of roots $z_1,\dots,z_n$ your inequality $P\cdot P'' + (\frac{1}{n}-1)P'^2 \leqslant 0$ may be rewritten as $\sum_{1\leqslant j<k\leqslant n} (\frac1{x-z_j}-\frac1{x-z_k})^2\geqslant 0$ for real $x$. Try a polynomial with roots $i,-i$, $1$ with multiplicity $m$, $0$ with multiplicity $m$. Then, ...

12

GH from MO gave in his answer a bound due to himself and Valentin Blomer of $O(\sigma(n))$. I thought it would be interesting to compute the $O$. Here I'm looking for an effective bound of the form $\leq C \Delta^{-\delta} \sigma(n) + o(\sigma(n))$ where the $C$ is explicit but the little $o$ need not be, so we only need be concerned with the Eisenstein term....

12

The identity can be rewritten as $$\sum_{\substack{|x|<p\\ 2|x}}\sum_{r|p^2-x^2}\left(\frac{-3}{r}\right)=p+2,$$ because for $x=0$ the inner sum is $1-1+1=1$. Writing $x=2c$, the identity becomes $$\sum_{|c|<p/2}\,\sum_{r|p^2-4c^2}\left(\frac{-3}{r}\right)=p+2.$$ The inner sum counts the number of integral representations $p^2-4c^2=a^2+ab+b^2$ divided ...

11

The quadratic case is as complex as the general case (up to a polynomial-time reduction). Given a set of polynomials $\{p_1,\dots,p_m\}$, you can express each $p_i$ by a straight-line program with instructions of the form $x_i:=c$ ($c\in\mathbb R$ a constant), $x_i:=x_j+x_k$, and $x_i:=x_j\cdot x_k$, which you can in turn translate back to quadratic ...

11

Thanks to BigM for the link to Ofir's MO Question 121913, which cites a 120-year-old paper of Hilbert for the result that the integral can get arbitrarily small as long as $b-a < 4$: D. Hilbert: Ein Beitrag zur Theorie des Legendre'schen Polynoms, Acta Math. 18 (1894), 155$-$159 If $b-a \geq 4$ then an elementary argument using properties of Legendre ...

11

Let $u_0=x_0+y_0\sqrt{p}$ be the smallest solution with $x_0,y_0>0$. (I assume you're talking about an upper bound for the smallest solution, since obviously there are solutions that are arbitrarily large.) Also let $h_p$ denote the class number of the ring of integers of $\mathbb Q(\sqrt p)$. Then Siegel's theorem says that $$\lim_{p\to\infty} \frac{\... 11 This is a nice observation about quadrics, I haven't seen it stated anywhere. It can be proved with the help of pencils of quadrics. 1) The curve of tangency is a circle. Consider the pencil of quadrics spanned by S and Q_1 (the set of quadrics whose equations are linear combinations of those for S and Q_1). All quadrics of the pencil are tangent ... 11 The function you are asking for is r_4(n), the number of ways to write n as a sum of four squares. The exact formula was discovered by Jacobi, and is given as$$\displaystyle r_4(n) = 8\sum_{\substack{d | n \\ 4 \nmid d}} d.

11

This is a well-known problem, called the Waring's problem of integral quadratic forms. Every semi-positive definite quadratic form in $n \leq 5$ variables is a sum of $n + 3$ squares of linear forms. This was proved by Chao Ko, but this can be explained by the fact that the quadratic form of sum of $n + 3$ squares has class number 1 if $n \leq 5$. There ...

10

Question 1: This is not really a question of genus theory but of elementary divisor theory. If $F$ is the quotient field of the Dedekind domain ${\mathfrak o}$ any two lattices $L_1, L_2$ of full rank on the $F$-vector space $V$ of dimension $n$ can be written as \$L_1={\mathfrak a}_1 x_1+ \dots + {\mathfrak a}_n x_n, L_2={\mathfrak b}_1{\mathfrak a}_1x_1+ \...

Only top voted, non community-wiki answers of a minimum length are eligible