Return to Question

Take $A,B,C,D$ pairwise coprime with $$n<A,B,C,D<2n$$ $$ n/4<|A−B|,|C−D|,|A−C|,|A−D|,|B−C|,|B−D|$$ and consider the space of solutions to $ACa+ADb+BCc+BDd=0$ spanned by $3\times 4$ matrix $$N=\begin{bmatrix} -D&C&0&0\\ -B&0&A&0\\ 0&0&-D&C \end{bmatrix}.$$

Denote the $\Bbb Q$-linear space spanned by rows of $N$ by $T_{A,B,C,D}\subseteq\Bbb Q^4$ and denote the set of non-zero $\Bbb Z$ vectors in $T_{A,B,C,D}$ by $T_{A,B,C,D}[\Bbb Z]^\star$.

Consider the quantity $\mu(A,B,C,D)=\min_{v\in T_{A,B,C,D}[\Bbb Z]^\star}\|v\|_\infty$ where $\|v\|_\infty$ is largest coordinate by magnitude of vector $v$. It is clear $\mu(A,B,C,D)\leq|a|,|b|,|c|,|d|$ at any $a,b,c,d$ with $ACa+ADb+BCc+BDd=0$ and $|a|+|b|+|c|+|d|\neq0$.

1. Is there a name for $\mu(A,B,C,D)$?

2. How is $\mu(A,B,C,D)$ distributed as a function of $A,B,C,D$ chosen with the constraints above (at least consider $A,B$ and $C,D$ each a coprime pair and $n<A,B,C,D<2n$) and what is its average value?

Simulations and heuristics suggest a value between $\Omega(n^{1/2})$ and $\Omega(n^{2/3})$ with $\Omega(n^{2/3})$ being the most likely possibility (at least probability $>1/n^\epsilon$ at any fixed $\epsilon>0$) of lower bound at least when $A,B,C,D$ are prime and hence is also the expected value at least when $A,B,C,D$ are prime.

Note here I am interested in lower bound in probabilities and expected value. There are worse case counterexamples. Upper bound for $\mu(A,B,C,D)$ is straightforward for shortest vector upper bounds and Bombieri-Vaaler bound on Siegel lemma. I need help on techniques to prove lower bound (at least is there a single choice of $A,B,C,D$ that comes close to upper bound is unclear.

This is where I get the $2/3$ heuristic. $$aBD+bBC+cAD+dAC=0$$ $$B(aD+bC)=-A(cD+dC)$$ $$cD+dC=\ell B$$ $$aD+bC=-\ell A$$

If size of $\ell$ is $n^\eta$ then size of $\ell B$ is size of $cD+dD$ is $n^{1+\eta}$. We have $n^{2\eta}$ values in $cd$ and $n^{2\eta}$ values in $ab$ and we want to hit $\ell B$ and $\ell A$ (a total of $2n^{\eta}$ possibilities) of a total of $n^{2(1+\eta)}$ possibilities. The expected intersection is $$\frac{n^{2\eta}n^{2\eta}2n^{\eta}}{n^{2(1+\eta)}}=\frac{2n^{3\eta}}{n^2}$$

If $3\eta>2$ or $2/3<\eta$ we have expected intersection $\gg1$.

Take $A,B,C,D$ pairwise coprime with $$n<A,B,C,D<2n$$ $$ n/4<|A−B|,|C−D|,|A−C|,|A−D|,|B−C|,|B−D|$$ and consider the space of solutions to $ACa+ADb+BCc+BDd=0$ spanned by $3\times 4$ matrix $$N=\begin{bmatrix} -D&C&0&0\\ -B&0&A&0\\ 0&0&-D&C \end{bmatrix}.$$

Denote the $\Bbb Q$-linear space spanned by rows of $N$ by $T_{A,B,C,D}\subseteq\Bbb Q^4$ and denote the set of non-zero $\Bbb Z$ vectors in $T_{A,B,C,D}$ by $T_{A,B,C,D}[\Bbb Z]^\star$.

Consider the quantity $\mu(A,B,C,D)=\min_{v\in T_{A,B,C,D}[\Bbb Z]^\star}\|v\|_\infty$ where $\|v\|_\infty$ is largest coordinate by magnitude of vector $v$. It is clear $\mu(A,B,C,D)\leq|a|,|b|,|c|,|d|$ at any $a,b,c,d$ with $ACa+ADb+BCc+BDd=0$ and $|a|+|b|+|c|+|d|\neq0$.

1. Is there a name for $\mu(A,B,C,D)$?

2. How is $\mu(A,B,C,D)$ distributed as a function of $A,B,C,D$ chosen with the constraints above (at least consider $A,B$ and $C,D$ each a coprime pair and $n<A,B,C,D<2n$) and what is its average value?

Simulations and heuristics suggest a value between $\Omega(n^{1/2})$ and $\Omega(n^{2/3})$ with $\Omega(n^{2/3})$ being the most likely possibility (at least probability $>1/n^\epsilon$ at any fixed $\epsilon>0$) of lower bound at least when $A,B,C,D$ are prime and hence is also the expected value at least when $A,B,C,D$ are prime.

Note here I am interested in lower bound in probabilities and expected value. There are worse case counterexamples.

Take $A,B,C,D$ pairwise coprime with $$n<A,B,C,D<2n$$ $$ n/4<|A−B|,|C−D|,|A−C|,|A−D|,|B−C|,|B−D|$$ and consider the space of solutions to $ACa+ADb+BCc+BDd=0$ spanned by $3\times 4$ matrix $$N=\begin{bmatrix} -D&C&0&0\\ -B&0&A&0\\ 0&0&-D&C \end{bmatrix}.$$

Denote the $\Bbb Q$-linear space spanned by rows of $N$ by $T_{A,B,C,D}\subseteq\Bbb Q^4$ and denote the set of non-zero $\Bbb Z$ vectors in $T_{A,B,C,D}$ by $T_{A,B,C,D}[\Bbb Z]^\star$.

Consider the quantity $\mu(A,B,C,D)=\min_{v\in T_{A,B,C,D}[\Bbb Z]^\star}\|v\|_\infty$ where $\|v\|_\infty$ is largest coordinate by magnitude of vector $v$. It is clear $\mu(A,B,C,D)\leq|a|,|b|,|c|,|d|$ at any $a,b,c,d$ with $ACa+ADb+BCc+BDd=0$ and $abcd\neq0$.

1. Is there a name for $\mu(A,B,C,D)$?

2. How is $\mu(A,B,C,D)$ distributed as a function of $A,B,C,D$ chosen with the constraints above (at least consider $A,B$ and $C,D$ each a coprime pair and $n<A,B,C,D<2n$) and what is its average value?

Simulations and heuristics suggest a value between $\Omega(n^{1/2})$ and $\Omega(n^{2/3})$ with $\Omega(n^{2/3})$ being the most likely possibility (at least probability $>1/n^\epsilon$ at any fixed $\epsilon>0$) of lower bound at least when $A,B,C,D$ are prime and hence is also the expected value at least when $A,B,C,D$ are prime.

Note here I am interested in probabilities and expected value. There are worse case counterexamples.

This is where I get the $2/3$ heuristic. $$aBD+bBC+cAD+dAC=0$$ $$B(aD+bC)=-A(cD+dC)$$ $$cD+dC=\ell B$$ $$aD+bC=-\ell A$$

If size of $\ell$ is $n^\eta$ then size of $\ell B$ is size of $cD+dD$ is $n^{1+\eta}$. We have $n^{2\eta}$ values in $cd$ and $n^{2\eta}$ values in $ab$ and we want to hit $\ell B$ and $\ell A$ (a total of $2n^{\eta}$ possibilities) of a total of $n^{2(1+\eta)}$ possibilities. The expected intersection is $$\frac{n^{2\eta}n^{2\eta}2n^{\eta}}{n^{2(1+\eta)}}=\frac{2n^{3\eta}}{n^2}$$

If $3\eta>2$ or $2/3<\eta$ we have expected intersection $\gg1$.

Take $A,B,C,D$ pairwise coprime with $$n<A,B,C,D<2n$$ $$ n/4<|A−B|,|C−D|,|A−C|,|A−D|,|B−C|,|B−D|$$ and consider the space of solutions to $ACa+ADb+BCc+BDd=0$ spanned by $3\times 4$ matrix $$N=\begin{bmatrix} -D&C&0&0\\ -B&0&A&0\\ 0&0&-D&C \end{bmatrix}.$$

Denote the $\Bbb Q$-linear space spanned by rows of $N$ by $T_{A,B,C,D}\subseteq\Bbb Q^4$ and denote the set of non-zero $\Bbb Z$ vectors in $T_{A,B,C,D}$ by $T_{A,B,C,D}[\Bbb Z]^\star$.

Consider the quantity $\mu(A,B,C,D)=\min_{v\in T_{A,B,C,D}[\Bbb Z]^\star}\|v\|_\infty$ where $\|v\|_\infty$ is largest coordinate by magnitude of vector $v$. It is clear $\mu(A,B,C,D)\leq|a|,|b|,|c|,|d|$ at any $a,b,c,d$ with $ACa+ADb+BCc+BDd=0$ and $|a|+|b|+|c|+|d|\neq0$.

1. Is there a name for $\mu(A,B,C,D)$?

2. How is $\mu(A,B,C,D)$ distributed as a function of $A,B,C,D$ chosen with the constraints above (at least consider $A,B$ and $C,D$ each a coprime pair and $n<A,B,C,D<2n$) and what is its average value?

Simulations and heuristics suggest a value between $\Omega(n^{1/2})$ and $\Omega(n^{2/3})$ with $\Omega(n^{2/3})$ being the most likely possibility (at least probability $>1/n^\epsilon$ at any fixed $\epsilon>0$) of lower bound at least when $A,B,C,D$ are prime and hence is also the expected value at least when $A,B,C,D$ are prime.

Note here I am interested in lower bound in probabilities and expected value. There are worse case counterexamples. Upper bound for $\mu(A,B,C,D)$ is straightforward for shortest vector upper bounds and Bombieri-Vaaler bound on Siegel lemma. I need help on techniques to prove lower bound (at least is there a single choice of $A,B,C,D$ that comes close to upper bound is unclear.

This is where I get the $2/3$ heuristic. $$aBD+bBC+cAD+dAC=0$$ $$B(aD+bC)=-A(cD+dC)$$ $$cD+dC=\ell B$$ $$aD+bC=-\ell A$$

If size of $\ell$ is $n^\eta$ then size of $\ell B$ is size of $cD+dD$ is $n^{1+\eta}$. We have $n^{2\eta}$ values in $cd$ and $n^{2\eta}$ values in $ab$ and we want to hit $\ell B$ and $\ell A$ (a total of $2n^{\eta}$ possibilities) of a total of $n^{2(1+\eta)}$ possibilities. The expected intersection is $$\frac{n^{2\eta}n^{2\eta}2n^{\eta}}{n^{2(1+\eta)}}=\frac{2n^{3\eta}}{n^2}$$

If $3\eta>2$ or $2/3<\eta$ we have expected intersection $\gg1$.

Take $A,B,C,D$ pairwise coprime with $$n<A,B,C,D<2n$$ $$ n/4<|A−B|,|C−D|,|A−C|,|A−D|,|B−C|,|B−D|$$ and consider the space of solutions to $ACa+ADb+BCc+BDd=0$ spanned by $3\times 4$ matrix $$N=\begin{bmatrix} -D&C&0&0\\ -B&0&A&0\\ 0&0&-D&C \end{bmatrix}.$$

Denote the $\Bbb Q$-linear space spanned by rows of $N$ by $T_{A,B,C,D}\subseteq\Bbb Q^4$ and denote the set of non-zero $\Bbb Z$ vectors in $T_{A,B,C,D}$ by $T_{A,B,C,D}[\Bbb Z]^\star$.

Consider the quantity $\mu(A,B,C,D)=\min_{v\in T_{A,B,C,D}[\Bbb Z]^\star}\|v\|_\infty$ where $\|v\|_\infty$ is largest coordinate by magnitude of vector $v$. It is clear $\mu(A,B,C,D)\leq|a|,|b|,|c|,|d|$ at any $a,b,c,d$ with $ACa+ADb+BCc+BDd=0$ and $abcd\neq0$.

1. Is there a name for $\mu(A,B,C,D)$?

2. How is $\mu(A,B,C,D)$ distributed as a function of $A,B,C,D$ chosen with the constraints above (at least consider $A,B$ and $C,D$ each a coprime pair and $n<A,B,C,D<2n$) and what is its average value?

Simulations and heuristics suggest a value between $\Omega(n^{1/2})$ and $\Omega(n^{2/3})$ with $\Omega(n^{2/3})$ being the most likely possibility (at least probability $>1/n^\epsilon$ at any fixed $\epsilon>0$) of lower bound at least when $A,B,C,D$ are prime and hence is also the expected value at least when $A,B,C,D$ are prime.

Note here I am interested in probabilities and expected value. There are worse case counterexamples.

Take $A,B,C,D$ pairwise coprime with $$n<A,B,C,D<2n$$ $$ n/4<|A−B|,|C−D|,|A−C|,|A−D|,|B−C|,|B−D|$$ and consider the space of solutions to $ACa+ADb+BCc+BDd=0$ spanned by $3\times 4$ matrix $$N=\begin{bmatrix} -D&C&0&0\\ -B&0&A&0\\ 0&0&-D&C \end{bmatrix}.$$

Denote the $\Bbb Q$-linear space spanned by rows of $N$ by $T_{A,B,C,D}\subseteq\Bbb Q^4$ and denote the set of non-zero $\Bbb Z$ vectors in $T_{A,B,C,D}$ by $T_{A,B,C,D}[\Bbb Z]^\star$.

Consider the quantity $\mu(A,B,C,D)=\min_{v\in T_{A,B,C,D}[\Bbb Z]^\star}\|v\|_\infty$ where $\|v\|_\infty$ is largest coordinate by magnitude of vector $v$. It is clear $\mu(A,B,C,D)\leq|a|,|b|,|c|,|d|$ at any $a,b,c,d$ with $ACa+ADb+BCc+BDd=0$ and $abcd\neq0$.

1. Is there a name for $\mu(A,B,C,D)$?

2. How is $\mu(A,B,C,D)$ distributed as a function of $A,B,C,D$ chosen with the constraints above (at least consider $A,B$ and $C,D$ each a coprime pair and $n<A,B,C,D<2n$) and what is its average value?

Simulations and heuristics suggest a value between $\Omega(n^{1/2})$ and $\Omega(n^{2/3})$ with $\Omega(n^{2/3})$ being the most likely possibility (at least probability $>1/n^\epsilon$ at any fixed $\epsilon>0$) of lower bound at least when $A,B,C,D$ are prime and hence is also the expected value at least when $A,B,C,D$ are prime.

Note here I am interested in probabilities and expected value. There are worse case counterexamples.

This is where I get the $2/3$ heuristic. $$aBD+bBC+cAD+dAC=0$$ $$B(aD+bC)=-A(cD+dC)$$ $$cD+dC=\ell B$$ $$aD+bC=-\ell A$$

If size of $\ell$ is $n^\eta$ then size of $\ell B$ is size of $cD+dD$ is $n^{1+\eta}$. We have $n^{2\eta}$ values in $cd$ and $n^{2\eta}$ values in $ab$ and we want to hit $\ell B$ and $\ell A$ (a total of $2n^{\eta}$ possibilities) of a total of $n^{2(1+\eta)}$ possibilities. The expected intersection is $$\frac{n^{2\eta}n^{2\eta}2n^{\eta}}{n^{2(1+\eta)}}=\frac{2n^{3\eta}}{n^2}$$

If $3\eta>2$ or $2/3<\eta$ we have expected intersection $\gg1$.