Optimum algorithms for generating Heron triangles; better count bounds & generators for d-simplices ====================Warren=D=Smith======Dec=2011====================================== I wondered if there were an algorithm to generate Heron triangles with diameter<N in N^(1+o(1)) time, which would be optimum. ["diameter" = longest edge. "Heron" = all sides, and face areas, and ..., volume are integer.] Sascha Kurz: On the generation of Heronian triangles, Serdica J. Comput. 2,2 (2008) 181-196 gave several algorithms for the triangle-generation task that run in N^(2+o(1)) time. We will now explain how to 1. Generate Heron triangles with diameter=N in N^o(1) time, and essentially no space. 2. Hence can generate Heron triangles with diameter<=N in N^(1+o(1)) time, and essentially no space. 3. Hence can generate Heron tetrahedra with diameter=N in N^o(1) time, and essentially no space. 4. Hence can generate Heron tetrahedra with diameter<=N in N^(1+o(1)) time, and essentially no space. Hence there are N^(1+o(1)) such tetrahedra, a new superior counting upper bound. 5. This keeps going to 4D, 5D, etc; works in any fixed dimension. PROOF: Let F(n) be the number of Heron triangles with diameter=n. IF we can prove an upper bound F(n)<n^o(1) it then would immediately follow that the number of Heron tetrahedra and Heron triangles with diameter<N is N^(1+o(1)). INCENTIVIZING REMARK: It is clear from previous bounds by me that F(N) has average order N^o(1), but we need to bound its maximum order. INCENTIVIZING REMARK: We know (a related problem) that the number of Pythagorean right triangles with hypotenuse C is C^o(1), in fact it is bounded by something like 4^G where G is the number of Gaussian primes in the factorization of C [there is actually a known formula for this count in terms of prime factorization of C, and there is a known fast algorithm dating to Hermite, also given by D.Shanks in his number theory book, also I think in Bach+Shallit's book, for finding all the representations of a given number as sum of two squares]. PROOF CONTINUES: In the Heron/Brahmagupta formulas for the side lengths a,b,c of a Heron triangle a = (n*n + k*k)*m; b = (m*m + k*k)*n; c = (m + n)*(m*n - k*k); we can argue the #divisors and factorizations a=X*Y of a is a^o(1) at most [Wigert bound] and the number of representations of a number X as sum of two squares like X=n*n+k*k is X^o(1) at most [Gaussian primes bound] hence if a is known the number of possible (k,m,n) it could have come from, is a^o(1) at most and we can find them all fast using fast integer and Gaussian integer factorization algorithms such as Dixon's rigorous "quadratic sieve"-like randomized factorizing algorithm. Similarly, if b is known, the number of possible (k,m,n) it could have come from, is b^o(1) at most. If c is known, it is a little trickier. We can factorize it into 2 factors in c^o(1) ways at most, c=X*Y, where X=m+n Y=m*n-k*k. If X and Y are known, then we can solve for n and m in terms of {X,Y,k} to find n,m = X/2 +- sqrt(X*X-4*Y-4*k*k)/2 hence the number of integer solutions n,m is bounded in terms of the number of ways that X*X-4*Y-4*k*k can be a square s*s. That is... in terms of the number of representations of X*X-4*Y = 4*k*k+s*s = (2*k)^2 + s^2 as a sum of two squares! But we already showed this is (X*X-4*Y)^o(1) <= c^o(1). Hence THEOREM: The number F(n) of Heron triangles with diameter=n, is F(n)<n^o(1), and they can be generated from n in n^o(1) time. RELATED WEAKER EARLIER RESULT: E.J. Ionascu, F. Luca, P.Stanica: Heron triangles with two fixed sides, J. Number Theory 126,1 (2007) 52-67. http://faculty.nps.edu/pstanica/research/heron.pdf studies the function H(a,b), which associates to every pair of positive integers a and b the number of positive integers c such that the triangle of sides a, b and c is Heron, i.e, has integral area. They prove H(a,b)<=4*NumberOfDivisors(a*b) and their method implicitly yields a way to generate all the c's from a,b in (a*b)^o(1) time. COROLLARY: The number of Heron tetrahedra with diameter=n, is <F(n)*F(n)*n^o(1)=n^o(1) and they can be generated from n in n^o(1) time. These constitute generation algorithms for Heron triangles with diameter<N that run in optimum time N^(1+o(1)) [well, optimum up to the vagueness in the "o(1)"] and optimum space [essentially no space]. It might however be that for Heron tetrahedra this is non-optimum. The question depends on how many Heron tetrahedra there are. This all gives us a new upper bound N^(1+o(1)) on the number of Heron tetrahedra of diameter<N. It also gives us an upper bound N^(1+o(1)) on the number of Heron triangles of diameter<N in a far simpler manner than my previous proof of that. But it might be that an as-yet-unknown better upper bound such as N^0.9 holds in which case our generator might not be optimum for tetrahedra. COROLLARY: The number of Heron 4-simplices with diameter=n, is <F(n)*F(n)*F(n)*n^(3*o(1))=n^o(1) and they can be generated from n in n^o(1) time. The three F(n)'s come from the 3 triangles sharing the longest edge, the n^(3*o(1)) come from the 3 simplex edges not in those 3 triangles. And so on... COROLLARY: In any fixed dimension d>0, the number of Heron d-simplices with diameter=n, is <F(n)^(d-1)*n^(((d+1)*d/2-2*d+1)*o(1))=n^o(1) and they can be generated from n in n^o(1) time. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)