The Count of Heron Triangles with Diameter<N grows like N^(1+o(1)) when N-->infinity ==================Warren D. Smith====December 2011================================== I believe I finally proved this. But in order to do it, I had to call in artillery support from one of the heaviest guns in mathematics, the "Green-Tao theorem." Just standing near that big gun has practically deafened me. And I suspect that the way I did that -- the "Counting Lemma" below -- will have many other uses too -- I don't see why counting Heron triangles should be the only use. A "Heron triangle" is a triangle with integer sidelengths and integer area. It is "primitive" if gcd(sidelengths)=1. Its "diameter" is its longest side. It was shown by Wm. F. Cheney: Heronian triangles, Amer. Math'l. Monthly 36,1 (1929) 22-28 that triangles with integer sides and rational area always have integer area which always is divisible by 6. (Fred Lunnon, myself, and Jan Fricke all rediscovered Cheney's theorem during the last 3 years... and quite likely Cheney himself rediscovered it too, since I find it hard to believe Brahmagupta did not know that.) THE MAIN THEOREM: The count of primitive (and also of nonprimitive, for that matter) Heron triangles with Diameter<N (more precisely the count of their sidelength triples a,b,c with a>=b>=c) when N-->infinity, is bounded between two functions of N which both grow like N^(1+o(1)). REMARK: Whether the triangles are primitive or not, does not matter because it is easily seen that the primitive and nonprimitive counts can at most differ by a factor bounded by a bounded power of logN at most, which is N^o(1). PROOF OF MAIN THEOREM LOWER BOUND (EASY): It has been known apparently since the ancient Indian mathematician Brahmagupta (598-668 AD) that every primitive Heron triangle (with sides a,b,c) arises from a = (n*n + k*k)*m; b = (m*m + k*k)*n; c = (m + n)*(m*n - k*k); and then divide out gcd(a,b,c) to primitivize it. Furthermore, this procedure for(n=1; (2*n+1)*(n+1)*n<=U; n++){ for(m=n+1; m*n*(m+n)<=U; m++){ for(k=1; k*k*(m+2*n)<=m*n*n ; k++){ a = (n*n + k*k)*m; b = (m*m + k*k)*n; c = (m + n)*(m*n - k*k); G = gcd(a,b,c); a /= G; b /= G; c /= G; output(a,b,c); }}} Will generate every primitive Heron triangle exactly once in the limit U-->infinity. Hence... CountOfHeronTrianglesOfDiameterUpToN > PositiveConstant * N. QED COUNTING LEMMA (DIFFICULT BUT HIGHLY USEFUL): Let R be a random integer [i.e. selected uniform in {1,2,3...,X} in the limit X large] or a random square [i.e. R=y*y where y selected uniform in {1,2,3...X} in same limit] or indeed a random Jth power for any fixed integer J>0. Let K be a fixed integer>=1, for example K=4. Let R=F1*F2*F3*...*FK be a random factorization of R into K parts, each a positive integer (different orderings counted multiply; "random" means uniform selection from all possible such factorizations). Let E be a fixed integer K-tuple, for example (-1, 1, 1, 1). THEN: The probability that the vector dot product F.E is zero, is asymptotically X^(o(1) - J/K) or less, in the limit X-->infinity. PROOF will be the bulk of this post, see below, but we defer it temporarily. PROOF OF MAIN THEOREM UPPER BOUND FROM THAT LEMMA:

From Heron's formula (Hero of Alexandria, lived about 10-70 AD) the area of triangle with sides a,b,c obeys 16*area^2 = (a+b+c) * (a+b-c) * (a+c-b) * (b+c-a). Choose a random square R as above as a putative value of 16*area^2. Plainly R<N^4 hence there are at most N^2 possible values of R. Choose a random factorization N=F1*F2*F3*F4. We can solve for a,b,c from F2,F3,F4 via linear equation solve. (This may yield rational a,b,c but the denominators if so are bounded so that does not affect any counts by more than a constant factor.) The probability that F1 really equals a+b+c=F2+F3+F4 is then seen via the LEMMA to be at most N^(o(1)-4/4) = N^(o(1)-1). We only get a Heron triangle if this probability comes true. Finally, use the fact proven by Carl Severin Wigert (life 1871–1941; see http://en.wikipedia.org/wiki/Divisor_function) that the number of divisors of N is <N^o(1), more precisely 2^(logN/loglogN + o(1)), [and hence the number of 4-factor factorizations of N is also N^o(1)]. Hence, the total number of Heron triangles of diameter<N is N^2 * N^(o(1)-1) * N^o(1) = N^(1+o(1)) at most. QED

Finally, to prove the difficult lemma. The proof will have 3 main ingredients. INGREDIENT 1: Linear equations in primes (or supersets thereof) =============================================================== THEOREM. Let S denote the set of primes, or any superset of them, within the positive integers. Let A be a kXn integer matrix, and let B be an integer k-vector. We ask the following basic question: are there integer-valued vectors x so all coordinates of Ax+B lie in S, and if so, how often? Answer: If no two rows of A are linearly dependent, and if (A,B) is not trivially obstructed -- that is, if for each prime p there exists an integer vector x causing all coordinates of Ax+B to be nonzero mod p and there are an infinite set of integer vectors x such that all coordinates of Ax+B are positive -- then: there exist an infinite set of x so that all coordinates of Ax+B are simultaneously is S, and further the multidimensional density of such x is just what you'd naively expect up to a constant factor. Specifically, for S=primes the number of vectors x that work with N/2<MinCoord(x)<=MaxCoord(x)<N is asymptotically (N^k)/(logN)^n * PositiveConstant where the constant depends on A and B (and is calculable explicitly); and for S a superset of the primes this bound increases by a factor at most of order (logN)^n [obviously]. REMARK: The linear dependence clause means you cannot use this to prove an infinity of twin primes exist. (Roughly speaking, you need at least 2 more unknowns than equations to solve linear equations in primes.) But you can use it to prove an infinity of all-prime K-term arithmetic progressions exist for any fixed K. ABOUT THE PROOF. This theorem was proven by Benjamin J. Green & Terence Tao: Linear equations in primes, Annals of Maths. (2) 171,3 (2010) 1753-1850 (98 pages!), http://arxiv.org/abs/math/0606088 depending on two conjectures they called MS(s) and GI(s). They proved conjecture MN(s) in Benjamin J. Green & Terence Tao: The Moebius function is strongly orthogonal to nilsequences, to appear, Annals of Maths, (23 pages) http://annals.math.princeton.edu/articles/3163 http://arxiv.org/pdf/0807.1736 And the conjecture GI(s) was proved in 2010 by B.J.Green+T.Tao+Tamar Ziegler: An inverse theorem for the Gowers $U^{s+1}[N]$-norm, submitted Annals of Maths http://arxiv.org/abs/1006.0205 http://arxiv.org/abs/1009.3998 (116 pages!) http://arxiv.org/abs/0911.5681 to appear in Glasgow J. Math. 49 pages. I warn you I have essentially no idea how Green, Tao, & Ziegler did it. This is over 200 pages of absolutely brutal mathematics involving super-advanced combinatorics, harmonic analysis, and number theory, at a fields medal level. Fortunately for the purpose of proving the Heron triangle result, I think this earlier weaker result Antal Balog: Linear equations in primes, Mathematika 39,2 (1992) 367-378 MR1203292 (93m:11103) suffices, which is only 12 pages. An earlier even weaker result of the same ilk (which is not good enough, far as I can see) is P.G.L. Dirichlet's prime density theorem (1837), see http://en.wikipedia.org/wiki/Dirichlet's_theorem_on_arithmetic_progressions Here is a brief description of the Green+Tao result, plagiarised+altered from math'l reviews: The paper under review is a landmark contribution to analytic number theory. The authors establish a vast multilinear generalization of the classical Dirichlet theorem on primes in arithmetic progressions. Consider the following problem: Let P denote the set of primes. Let A be a $k\times n$ integer matrix, and let B be an integer vector. We ask the following basic question: are there integer-valued vectors x so all coordinates of $Ax+B$ are prime, and if so, how often? Answer: If no two rows of A are linearly dependent, and if (A,B) is not trivially losing -- that is, if for each prime p there exists an integer vector x causing all coordinates of Ax+B to be nonzero mod p and there are an infinite set of integer vectors x such that all coordinates of Ax+B are positive -- then there exist an infinite set of x so that all coordinates of Ax+B are simultaneously prime, and further the multidimensional density of such x is just what you'd naively expect up to a constant factor (and the constant factor always is calculable explicitly, with more work). INGREDIENT 2: Kalai's algorithm for generating random numbers in factored form: =============================================================================== Adam Kalai: Generating Random Factored Numbers Easily, Journal of Cryptology 16,4 (2003) 179-193 http://ttic.uchicago.edu/~kalai/papers/old_papers/factorcryptology.pdf Kalai's algorithm is incredibly simple. Here it is: Input: Integer n>0. Output: Exactly-uniformly random number 1<=r<=n with factorization into primes. Step 1: Generate a sequence n>=s1>=s2>=...>=sL by choosing s1 in {1,2,3,...,n} uniformly at random, then and s[i+1] uniformly at random from {1,2,3,...,s[i]}, until reaching 1. Step 2: Let r be the product of the PRIME s[i]'s. Step 3: If r<=n, output r with probability r/n. Otherwise, RESTART. COMMENT ON ALGORITHM: Runs in expected number O(log(n)^2) of primality tests and O(log(n)) restarts. Note the "triangular density rejection step" in step 3. This triangular is not uniform, but within the interval [n/2, n] it is uniform to within a factor of sqrt(2). INGREDIENT 3: Known facts about max number of divisors an integer N can have ============================================================================ We already mentioned Wigert's bound #divisors(N) <= N^o(1). Actually, if you want to try to get the strongest possible form of the thing I am sloppily calling "o(1)" then look into Erdos-Kac theorem of 1939-1941 and related work about how many prime factors random integers have and its asymptotic distribution. http://en.wikipedia.org/wiki/Erdos–Kac_theorem Peter DTA Elliott: Probabilistic Number Theory vols 1 & 2, Springer 1980, (GMW 239&240); QA241.7.E55. This seems to be a stronger result that would allow us to safely ignore numbers N with more than about sqrt(logN)*loglogN prime factors as so rare that they cannot affect the count much. Anyhow something like this ought to exist and be stronger than the Wigert bound, but I do not need it. FINALE: HOW TO MAKE A PROOF OUT OF THOSE 3 INGREDIENTS: ======================================================== We use Kalai's algorithm to generate (the Jth powers of) uniform random numbers. Then we argue using Green-Tao-Ziegler plus Kalai's analysis that the probability that the 4th factor is the sum of the other 3 factors, is at most about what you'd expect it to be (up to distortion by constant and log^power factors at most, asymptotically... anyhow clearly N^o(1) factors at most). Note, in Kalai's algorithm, certain things get distorted away from uniform density. The distortion in the interval [n/2, n] is at most by a factor of sqrt(2). If T things are multiplied the density distortion factor could be as large as log(X) * 2^(T/2). There might be considerably larger distortion on the decrease side -- this bound is for increase-factor -- but that is ok since we are only asking for an upper bound on an integrated probability density. However, T for us is going to be at most T=O(logX/loglogX) by the Wigert bound on #prime factors of X. Also the Wigert bound on #divisors and hence #factorizations of X into K parts (K and J are fixed, remember) will be X^o(1). These distortions are going to alter the Green-Tao-Ziegler count estimates (which were based on uniform density) by at most a factor X^o(1). QED. REMARK: I think the "o(1)" more precisely should be PositiveConstant / loglogN + lower order terms which explains why our computers haven't clearly realized that the Heron Triangle Count is N^(1+o(1)). The computer counts think it is behaving more like N^1.4. The reason is loglogN goes to infinity too slowly for computers to realize that o(1) goes to 0. [Using Erdos-Kac or something like that, my expression for the "o(1)" could probably be improved to something better, but I think it'd still slow enough to blur the vision of computers.] (End of proof). -- Warren D. Smith http://RangeVoting.org  <-- add your endorsement (by clicking "endorse" as 1st step)