A power improvement in the Heilbronn triangle lower bound

Proof. The determinant of the lattice generated by the v_i is an integer multiple of \det L and is at most \prod_i\lambda_i. For the reverse bound, choose orthonormal coordinates whose first j directions span v_1,\ldots,v_j for each j. Let

If a nonzero lattice vector in Q has last nonzero coordinate j, it lies outside the preceding span and has length strictly less than \lambda_j, a contradiction. The translates of Q/2 by L are therefore disjoint. Integrating their indicator functions over a fundamental domain of L gives \operatorname{vol}(Q/2)\le\det L. Since \operatorname{vol}(Q/2)=s^{-s/2}\prod_i\lambda_i, the result follows.□

Proof. For the first assertion let L_0=\mathbb Zv_1+\mathbb Zv_2. A half-open fundamental parallelogram for L_0 has diameter at most \lambda_1+\lambda_2\le2R. For each coset of L_0, attach such a parallelogram to every point in the ball. The parallelograms are disjoint and lie in a disk of radius at most 3R in the affine span. Thus each coset contributes at most 9\pi R^2/\det L_0 points. Summing over [L:L_0] cosets proves the first assertion. For the second, every lattice vector outside \mathbb Rv_1 has length at least \lambda_2. The lattice on \mathbb Rv_1 is \mathbb Zv_1, since a shorter generator would contradict the choice of v_1. Counting its multiples proves the bound.□

Proof. Choose u\in\Lambda with y\cdot u=g. The map v\mapsto y\cdot v/g maps \Lambda onto \mathbb Z, has kernel \Lambda\cap y^\perp, and splits by 1\mapsto u. Hence a basis of the kernel together with u is a basis of \Lambda. The height of u above y^\perp is g/|y|, which proves the formula. For \Lambda=\mathbb Z^3, primitivity gives g=1.□

Proof. The columns u_2,u_3 are independent. Choose a primitive normal y to their plane, fixing its sign by requiring its first nonzero coordinate to be positive. Then u_2\times u_3=a y for some nonzero integer a, so |y|\le R_2R_3. If \mu_1,\mu_2 are the successive lengths of L_y, the columns imply \mu_1\le R_3 and \mu_2\le R_2.

For fixed u_2,u_3, the determinant equation is u_1\cdot y=t/a. Its integral solutions are either absent or form a translate of L_y. By Lemmas 2.2 and 2.3, at most C R_1^2/|y| satisfy the first-column bound; the required hypothesis is \mu_2\le R_2\le R_1. For a fixed normal y, there are likewise at most C R_2^2/|y| choices for u_2.

First suppose \mu_2\le R_3. There are at most C R_3^2/|y| choices for u_3. The resulting bound, summed over normals, is

The last estimate follows by splitting the integer vectors into dyadic shells; a shell of radius Y\ge1 has O(Y^3) vectors.

It remains to treat \mu_2>R_3. Group the normals by powers of two U,Z\ge1 with

Lemma 2.1 gives |y|\asymp UZ. There are at most C U^4Z^2 normals in such a group. Indeed, choose a shortest nonzero vector z\in L_y. It is primitive in \mathbb Z^3, because division by a common divisor would produce a shorter vector in L_y. Its length is in [U,2U), giving O(U^3) choices. For each such z, the possible normals lie in L_z and have length less than 4UZ. If \nu_1,\nu_2 are the successive lengths of L_z, integrality gives \nu_1\ge1, and the preceding lemmas give

Consequently Lemma 2.2, applied at radius 4UZ, bounds their number by C(UZ)^2/|z|\le C UZ^2. This proves the claimed normal count.

For each of these normals, all eligible third columns lie on the line of a shortest vector. Lemma 2.2 gives at most 1+2R_3/\mu_1\ll R_3/U choices, since U\le\mu_1\le R_3. Thus the contribution of one dyadic group is at most

There are O(\log(2R_3)\log(2R_2)) groups, since 1\le U\le R_3 and 1\le Z\le R_2. Combining both cases proves the assertion.□

Proof. Let V be the matrix whose rows are the successive shortest vectors v_1,v_2,v_3, and let \Lambda_0 be their integer span. By Lemma 2.1,

Since the finite group \Lambda/\Lambda_0 has order m, each u\in\Lambda has coordinates in m^{-1}\mathbb Z relative to this basis. If u=\sum_j\alpha_jv_j and |u|\le X, Cramer’s rule gives

Thus the map A\mapsto Q=mAV^{-1} is injective and takes the matrices under consideration to integral matrices. Their common determinant is m^3t/\det V\ne0. If this number is not an integer, there are no such matrices; otherwise Lemma 2.4 applies.

The jth column of Q has length at most R_j=C_0X/\lambda_j, where C_0 is an absolute constant chosen sufficiently large. These radii satisfy R_1\ge R_2\ge R_3\ge1. Moreover, integrality of \Lambda gives \lambda_j\ge1, and Lemma 2.1 gives

The bound in Lemma 2.4 is therefore the claimed one.□

Proof. List the degree-d monomials in 3d variables as m_1,\ldots,m_M. Expand \mathcal N in products m_p(X^{(1)})m_q(X^{(2)})m_s(X^{(3)}). If two of p,q,s coincide, the coefficient equals its negative under the corresponding transposition, and hence is zero because r is odd. For each p<q<s, let c_{pqs} be the coefficient of m_p(X^{(1)})m_q(X^{(2)})m_s(X^{(3)}). Alternation identifies the other five coefficients with the signs in

Enumerate the T triples p<q<s by a, and take

This argument uses no division by 3!, so it applies also when r=3.□

Proof. Write c_{iv}^{(j)} for the digit at row i, position v, in column j. Form the integer polynomial

For a fixed exponent u and each of the six determinant permutations, choosing the first two digit positions determines the third. Therefore

Alternatively expanding by rows, \gamma_{k-1} is the sum of determinants of digit rows at positions whose sum is k-1. Modulo r, all terms with an undesignated position vanish. By (3.7), the surviving terms are exactly those in (3.3), evaluated at the three label vectors. Consequently

which is nonzero by (3.4). In particular |\gamma_{k-1}|\ge1 as an integer.

The integer

represents \det C modulo h, because all omitted terms in F(B) are divisible by B^k. Since B-1\ge100k^2L^3, the coefficient bound gives

It follows that

By (3.10), every other representative S_C+mh, m\in\mathbb Z\setminus\{0\}, has absolute value greater than h/2>\tau. This proves the assertion.□

Proof. Move a unit entry into the first position, scale it to 1, and clear the rest of its row and column by invertible operations. In the remaining 2\times2 block choose a nonzero entry of least B-adic valuation b, move it to the first position of that block, and multiply by a unit to make it B^b. Every other entry of the block is divisible by B^b in R_h, so row and column subtraction clear its row and column. The final entry is still divisible by B^b; scaling it by a unit makes it B^e with b\leq e\leq k. If the block is zero, take b=e=k. This proves the stated form, including all zero-pivot cases.

Invertible row and column operations preserve the ideal generated by the 2\times2 minors: each new minor is a linear combination of old minors, and the inverse operations give the reverse inclusion. For the diagonal matrix this ideal is B^bR_h. Its image modulo B^j is zero exactly when b\geq j, proving the last assertion and, in particular, showing that b is independent of the diagonalization.

Write \mathscr M for the row span of C. Left multiplication by P does not change the row span, while multiplication on the right by Q is an automorphism of R_h^3. Hence

The reduction map identifies \mathbb Z^3/\Lambda_C with R_h^3/\mathscr M, which proves the index formula. Since D divides E, the diagonal row span contains ER_h^3. Right multiplication by Q preserves ER_h^3, so \mathscr M also contains ER_h^3. Taking inverse images proves the containment in (4.1).□

Proof. Let \mathcal G=\operatorname{GL}_3(R_h), and let \mathcal H be the stabilizer of C under left multiplication. Conjugation by P identifies \mathcal H with the stabilizer of \operatorname{diag}(1,D,E) and preserves determinants. An element of this latter stabilizer has first column exactly (1,0,0)^{\mathsf T}. Its second column differs from (0,1,0)^{\mathsf T} by three entries annihilated by D, and its third column differs from (0,0,1)^{\mathsf T} by three entries annihilated by E. The respective annihilators have D and E elements. Discarding the invertibility condition gives

For every unit u\in R_h^\times with u\equiv1\pmod{h/E}, the matrix \operatorname{diag}(1,1,u) stabilizes \operatorname{diag}(1,D,E). If e<k, there are exactly E such units. If e=k, this congruence imposes no restriction, so there are \varphi(h)=(1-B^{-1})E of them. Consequently, in all cases,

Here \det\mathcal H denotes the image of the determinant homomorphism on \mathcal H.

The determinant map from \mathcal G onto R_h^\times has kernel \operatorname{SL}_3(R_h). Applying the orbit–stabilizer formula in these two groups gives the exact identity

Reduction modulo B shows that

Together with (4.3) and (4.4), this proves (4.2), for example with c_0=21/64. Every fiber of the map G\mapsto GC is a coset of its stabilizer, which proves uniformity. The assertions about row spans and determinants follow directly from invertibility and \det G=1.□

Proof. Every prescribed digit set has exactly L/r elements. Since the lowest digit belongs to \{1,\ldots,L\} and L<B, every entry of C is a unit in R_h.

In addition to the three labels, condition on the complete first column of C and the first entries of its other two columns. If b\geq j, Lemma 4.1 implies, for i,v\in\{2,3\},

The right sides are fixed under this conditioning. Each congruence determines the first j base-B digits of its entry, since all chosen digits lie between 0 and B-1. It therefore has probability either zero or (r/L)^j. The four entries use disjoint independent digit draws, even if their labels agree. Their joint probability is at most (r/L)^{4j}. Averaging over the additional conditioning proves (4.5), including j=k.

Finally, the pointwise identity

and (4.5) give (4.6).□

Proof. Choose a nonsquare \nu\in\mathbb F_q and put

The form Q vanishes only at (0,0). On a line with nonzero direction (v_1,v_2) in its first two coordinates, the equation defining \Gamma is a quadratic equation in the line parameter with nonzero leading coefficient Q(v_1,v_2). Such a line meets \Gamma at most twice. A line with direction (0,0,v_3) meets \Gamma exactly once. Thus \Gamma, and every translate of it, has the asserted line property.

For a uniform b\in\mathbb F_q^3, every point belongs to b+\Gamma with probability |\Gamma|/q^3=1/q. Therefore the average of |(b+\Gamma)\cap\{0,\ldots,w-1\}^3| is w^3/q. Choose a translate attaining at least this average and take its intersection with the box.□

Proof. For each integer 1\le m\le3H<q, multiplication by m permutes \mathbb F_q. Since 3Hw<q/2, a uniform shift violates the condition for this m with probability (6Hw+1)/q. The union bound gives

Thus the required uniform choice of a is defined. Invertible affine maps preserve cardinality and the line property. If a+v=0 for some v\in S, then \|a_1\|_q\le w-1\le3Hw, contrary to the condition with m=1. Hence 0\notin V.

Write u^{(i)}=G_q(a+v^{(i)}) with v^{(i)}\in S, and let m=x_1+x_2+x_3. If m\ne0, then 1\le |m|\le3H. Applying G_q^{-1} to (5.5) and taking first coordinates gives

The integer on the right, using the representatives 0\le v^{(i)}_1<w, has absolute value at most 3H(w-1). Since \|ma_1\|_q=\||m|a_1\|_q, this contradicts (5.3).

If m=0, the coefficients in (5.5) have sum zero also in \mathbb F_q. They are not all zero there, since x\ne0 and |x_i|\le H<q. Such a relation contradicts affine independence: substituting x_3=-x_1-x_2 would give a nontrivial linear relation between u^{(1)}-u^{(3)} and u^{(2)}-u^{(3)}. Finally, three distinct elements of V are affinely independent by the line property.□

Proof. First replace the allowed shift by an unconditional uniform a\in\mathbb F_q^3. Under this replacement the map v\mapsto G_qv+G_qa is uniform in the affine group: conditional on G_q, its translation G_qa is uniform. Conditioning back on a\in\mathcal A increases the probability of any event by at most two, by Lemma 5.2.

The affine group acts transitively on the ordered affinely independent triples in \mathbb F_q^3, whose number is

There are s(s-1)(s-2) such triples in S. Therefore, for an affinely independent triple of columns,

For the other two bounds, fix any allowed a and put S_a=a+S. If two specified target columns are linearly independent, their inverse images under a uniform G_q are uniform among the (q^3-1)(q^3-q) ordered independent pairs. At most s^2 of these pairs belong to S_a^2. Requiring all three columns to belong to G_qS_a can only reduce this probability. Consequently,

whenever the target matrix has rank at least two. This estimate holds for each allowed shift, so also after averaging over a.

If any target column is zero, its inclusion probability is zero. Otherwise fix one target column. Its inverse image under G_q is uniform among the q^3-1 nonzero vectors, and S_a consists of s nonzero vectors. Thus

This also covers all patterns of equal columns. The remaining assertions follow from the line property and short-relation conclusion in Lemma 5.2.□

Proof. Equality of the projections is equivalent to proportionality of u and v, because their third coordinates are positive. Every column in \mathcal B is a positive integer multiple of a unique primitive integral vector z with z_3>0. The number of its multiples in \mathcal B is at most \sqrt6N/|z|. Therefore the total number of ordered proportional pairs in \mathcal B^2, including equal columns, is at most

For the last estimate, dyadic shells of radius R contain O(R^3) integral vectors and contribute O(R) to the sum.

Condition on both columns’ residues at both moduli and on the shared random choices. Their lifts are independent, each uniform on exactly (N/(hq))^3 columns. The preceding count bounds the number of proportional pairs within any two such sets of lifts. Dividing by (N/(hq))^6 and averaging proves the claim.□

Proof. The matrix G_hC is uniform on \mathcal O, since every point of an orbit has the same number of group elements mapping C to it. Given V, the three auxiliary residues are independent and uniform on its s elements. Consequently, for each specified ordered triple of auxiliary residues, its probability is its inclusion probability in V, divided by s^3. This remains true when some residues coincide. Independence of the main and auxiliary choices and the exact number of lifts give, for each fixed integral A with A\bmod h\in\mathcal O, the conditional probability

For other matrices the probability is zero. Summation proves the identity.□

Proof. Suppose first that t\ne0. Since 0<|t|\le\tau<q, the reduction of A modulo q has rank three. Its columns are therefore affinely independent, and Proposition 5.3 gives W(A)\ll1. Every row of A belongs to \Lambda and has norm less than 4N. Moreover E\mathbb Z^3\subseteq\Lambda gives \lambda_3(\Lambda)\le E\le h<4N. Proposition 2.5, applied with X=4N, proves the estimate.

For t=0, Proposition 7.1 below proves the stronger bound O(\log(2N)N^6/I^2) for all matrices with rows in \Lambda and pairwise distinct projected columns. The orbit restriction only reduces this set, so it gives the claimed estimate as well.□

Proof. Conditional on the labels and digit matrix C, the probability is zero when all labels are distinct. Otherwise Lemma 6.2 and Proposition 6.3, together with the bound |\mathcal O|\gg h^8/(D^3E^2) from (4.2), bound it by

Let F be the event that two of the three labels agree. The uniform conditional moment estimate (4.7) gives

This step uses the moment estimate for every fixed label triple, including repeated labels; the corresponding digit draws remain independent. Averaging the conditional bound proves the corollary.□

Proof. Primitivity gives x\cdot\mathbb Z^3=\mathbb Z. Since E\mathbb Z^3\subseteq\Lambda, we have E\mathbb Z\subseteq g(x)\mathbb Z, so g(x)\mid E. Lemma 2.3 gives the formula for J_x, and g(x)^3/I\le E^2/D\le h^2.

Primitivity also implies \bar x\ne0, with no restriction on the size of x. To prove surjectivity, choose z\in\mathbb Z^3 with x\cdot z=1. If an integral lift v of a point of \Pi_x has x\cdot v=qa, then v-qaz\in\mathbb Z^3\cap x^\perp is another lift of the same point. Thus \mathbb Z^3\cap x^\perp reduces onto \Pi_x. Its multiple by E lies in \Lambda_x and still reduces onto \Pi_x, because q\nmid E.

Finally, a triple counted in (7.3) contains two independent vectors of length at most 4N. Therefore the second successive minimum of \Gamma is at most 4N whenever the count is nonzero. Lemma 2.2 then bounds the choices for each vector by O(N^2/\det\Gamma), and \det\Gamma=mJ_x.□

Proof. Since g(x)\mid B^e, write g(x)=B^{a(x)} with 0\le a(x)\le e. For 0\le j\le e, the condition B^j\mid g(x) is equivalent to Cx=0\pmod{B^j}. Indeed, if \widetilde C is any integral lift of C, then \Lambda is the sum of the integral row span of \widetilde C and h\mathbb Z^3, and B^j\mid h. The diagonal form of C shows that the fraction of residue classes modulo B^j satisfying this congruence is

Indeed, the first diagonal coordinate must vanish, the second must be divisible by B^{\max(j-b,0)}, and the third is unrestricted since j\le e.

Because R\ge h\ge B^j, each residue class contains O((R/B^j)^3) integral vectors of length less than 2R. We may discard primitivity for this upper bound. Consequently,

The exponents in the last sum strictly increase to b+e, so its bound is uniform in B. Finally, h\ge2 implies H/2=h^2/2\ge h.□

Proof of Proposition 7.1. Every A\in\mathcal Z has rational rank two. Indeed, its columns are nonzero, and no two are proportional because their projections are distinct. Its right nullspace therefore has a primitive integral generator x, unique up to sign. Every coordinate of x is nonzero: otherwise the relation would make two columns proportional. Taking the cross product of two independent rows and dividing by the gcd of its coordinates gives

Every row of A lies in \Lambda_x and has length at most 4N. Thus x records a relation among the columns, while the rows are lattice vectors perpendicular to x. We may sum over both choices of sign of x for an upper bound.

Partition the possible vectors into dyadic shells R\le |x|<2R, R=1,2,4,\ldots. By (7.5), there are O(\log(2N)) shells. We will bound the weighted contribution of each shell by O(N^6/I^2). For a fixed primitive x in such a shell, a condition confining every row to an index-m sublattice of \Lambda_x gives at most

matrices of rational rank two, by (7.3) and J_x=I|x|/g(x). In the affine case we will sum g(x)^3 using Lemma 7.3. In the equal-pair cases we instead use g(x)^3\le Ih^2, together with an extra row congruence or a smaller number of possible null vectors. The support statement and the three weight bounds in Proposition 5.3 give the following exhaustive cases.

Affinely independent residues. If W(A)>0 and the columns of A\bmod q are affinely independent, Lemma 5.2 excludes the relation Ax=0 when |x|\le H. To see both parts of this exclusion, if x_1+x_2+x_3\ne0 use the restricted shift; if the sum is zero, use affine independence and \bar x\ne0. Hence a contributing shell satisfies R>H/2. Using W(A)\ll1, (7.6) with m=1, and Lemma 7.3, its contribution is at most

An equal pair with an additional equation. Every other matrix of positive weight has two equal columns modulo q. Fix one pair i<j with this property, and put \delta=\mathbf e_i-\mathbf e_j, where the \mathbf e_i are the standard basis vectors. Summing over the three pairs only changes the implied constant. First suppose that \bar x\notin\mathbb F_q\delta. The functional v\mapsto v\cdot\delta is nonzero on \Pi_x: the annihilator of \Pi_x is precisely \mathbb F_q\bar x. By Lemma 7.2, the rows of A therefore belong to the index-q sublattice

There are O(R^3) integral x in any shell. Using (7.6) with m=q, the pointwise bound g(x)^3\le Ih^2, and W(A)\ll(q^3/s)^2, the contribution is at most

Here and below we use q^3/s\ll qH^6=qh^{12} and q>h^{100}. This argument includes matrices of every rank modulo q.

An equal pair without an additional equation. It remains to consider \bar x\in\mathbb F_q\delta. The coordinate of x outside the pair i,j is divisible by q and, by (7.5), is a nonzero integer. Thus |x|\ge q, and a contributing shell has R>q/2. The nonzero multiples of \delta give q-1 residue classes for x modulo q. Each class contains O((1+R/q)^3) vectors of length less than 2R, so the number of possible x in this shell is

Rank at least two modulo q. The weight bound W(A)\ll q^3/s now gives

for the contribution of the shell.

Rank at most one modulo q. All rows reduce into one of the q+1 one-dimensional linear subspaces of \Pi_x. This also covers the zero row space. For each such line \ell\subseteq\Pi_x, surjectivity in Lemma 7.2 shows that

has index q in \Lambda_x. Formula (7.3) thus bounds the rank-two rational row triples, summed over all these lines, by

Using (7.9) and the general weight bound, the weighted contribution is at most

The affine and equal-pair cases cover the support of W. Their bounds are uniform over the dyadic shells, so summing over the O(\log(2N)) shells proves (7.1).□

Proof of Theorem 1.1. Keep the parameters constructed above, with d=41, and set

Here k\ge2 and B is an odd prime, so \tau\ge1. Take 2n_r samples with the shared random choices and independent conditional draws specified in Section 6. Let Z count the unordered pairs of sample indices with equal projected points, plus the unordered triples whose projected points are pairwise distinct and whose determinant has absolute value at most \tau. Linearity of expectation, Lemma 6.1, and Corollary 6.4 give

No independence between the counted events is needed.

Both terms tend to zero. Indeed, N=(hq)^{10} and \tau\ge1 give

For the other term, the definition of n_r gives

Since B^{k-1}\ge3, the definition of \tau implies \tau\ge B^{k-1}/3, and hence h/\tau\le3B=O_k(r^{30}). The bounds B=O_k(r^{30}), q\le2h^{100}, and N=(hq)^{10} also give \log(2N)=O_k(\log r). Thus the second term in (8.2) is O_k((\log r)^2r^{-9})=o(1). Thus \mathbb EZ=o(n_r).

For sufficiently large r, choose an outcome with Z<n_r. For each violating pair or triple in that outcome, mark one of its indices for deletion. This marks at most Z indices and meets every original violation. After deleting all marked indices, at least n_r remain; retain any n_r of them. Their projections form a set P_r of n_r distinct points in [0,1)^2, and every triple of retained columns satisfies |\det A|>\tau. In particular, the construction excludes every zero-area triple as well.

For a retained triple, divide the jth column of A by its positive third coordinate A_{3j}. The resulting columns have the form (p_{j1},p_{j2},1)^{\mathsf T}, so the determinant formula for triangle area gives the exact identity

Since N\le A_{3j}<2N for each j, every retained triangle has area at least \tau/(16N^3). Consequently

Also \tau<h and N\ge h^{10} give a_r>rh^{29/2}\to\infty. Hence n_r\to\infty and eventually n_r\ge a_r/2. Combining this with (8.4) yields

We now express both the cardinality and the area bound in terms of r. The parameter choices give

Consequently, if

then

Since a_r/2\le n_r\le a_r for sufficiently large r, there are fixed constants A_k,D_k>0 such that

for every sufficiently large prime r. In particular, put

The upper bound in (8.6) gives r^2\ge D_k^{-\eta}n_r^\eta. Combining this with (8.5), we obtain

Thus the same cardinality estimate that will permit interpolation also converts the factor r^2 into a fixed power of the number of points.

For a sufficiently large integer n, put m=\lceil(n/A_k)^{1/\alpha}\rceil. Lemma 3.2 supplies a prime r with m<r\le2m. Once (n/A_k)^{1/\alpha}\ge1, we have m\le2(n/A_k)^{1/\alpha}, so (8.6) gives

This uses only the two-sided cardinality bounds, not monotonicity of n_r. Retain any n points of P_r. Deleting points cannot decrease the minimum triangle area. Since 0<\eta<2, (8.8) therefore yields

Taking c_1=c_*C_k^{-2+\eta} proves Theorem 1.1. All constants are absolute because k is fixed independently of r and n. The formula (8.7) is explicit; no attempt has been made to optimize the construction parameters.□

Proof of Lemma 3.2. Write P(x)=\prod_{p\le x}p, where the product is over primes. First, P(x)<4^x for x\ge1. It suffices to prove this for integer x by induction. The cases x=1,2 are immediate. An even integer x>2 is composite, so P(x)=P(x-1). For x=2m+1, every prime in (m+1,2m+1] divides \binom{2m+1}{m}. The two central binomial coefficients are equal and their sum is strictly less than 2^{2m+1}, whence \binom{2m+1}{m}<4^m. Thus

Suppose now that there is no prime in (n,2n]. The largest binomial coefficient in (1+1)^{2n} gives \binom{2n}{n}\ge4^n/(2n+1). For any prime p, its exponent in this coefficient is

Each summand is zero or one, so the entire prime power contributed by p is at most 2n. The primes at most \sqrt{2n} therefore contribute at most (2n)^{\sqrt{2n}}. Larger primes have exponent at most one. Those in (2n/3,n] have exponent zero, and by assumption there are none in (n,2n]. For sufficiently large n it follows that

Taking logarithms contradicts (n/3)\log4>\sqrt{2n}\log(2n)+\log(2n+1) for sufficiently large n.□