-1
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

We will assume that $n<A,B,C,D<2n$ and $\gcd(A,B)=\gcd(C,D)=1$. For $x,y,z\in\mathbb{Q}$, we write $v(x,y,z)$ for the vector $$\pmatrix{\frac{x}{C}&\frac{y}{C}&\frac{z}{C}}N\in\mathbb{Q}^4. $$

Lemma 1. For $x,y,z\in\mathbb{Q}$, it holds that $v(x,y,z)\in\mathbb{Z}^4$ iff $x,y,z\in\mathbb{Z}$ and the following conditions hold: $$\begin{eqnarray*} xD+yB\equiv 0\pmod{C},\\ zD-yA\equiv 0\pmod{C}.\\ \end{eqnarray*} $$

Proof. A direct calculation shows $$v(x,y,z) =\pmatrix{\frac{-yB-xD}{C}&x&\frac{yA-zD}{C}&z}, $$ which immediately shows the implication from right to left. Assume then that the vector belongs to $\mathbb{Z}^4$. Then obviously $x,z\in\mathbb{Z}$. It follows that $yA,yB\in\mathbb{Z}$, which implies $y\in\mathbb{Z}$ by the assumption $\gcd(A,B)=1$.

We will call $x,y,z$ such as above witnesses for $\mu(A,B,C,D)\le\|v(x,y,z)\|_\infty$.

Lemma 2. For $x,y,z\in\mathbb{Q}$, it holds that $$\frac{\max(|x|,|y|,|z|)}{4}\le\|v(x,y,z)\|_\infty\le 4\max(|x|,|y|,|z|). $$ Proof. Write $v(x,y,z)=\pmatrix{u&x&v&z}$. For the first inequality, it suffices to note that $$|y|=\frac{|vC+zD|}{A}\le\frac{C}{A}|v|+\frac{D}{A}|z|\le 2(|v|+|z|)\le 4\|v(x,y,z)\|_\infty. $$ For the second inequality, we get $$|u|\le\frac{B}{C}|y|+\frac{D}{C}|x|\le 2(|x|+|y|)\le 4\max(|x|,|y|,|z|) $$ and similarly the same bound for $v$.

Theorem 1. There is a constant $K$ (independent of $n$) such that for all choices of $A,B,C,D$ as above, it holds that $\mu(A,B,C,D)<Kn^{2/3}$.

Proof. For $y\in\mathbb{N}$, let $f(y)$ and $g(y)$ be the unique integers such that $f(y)D+yB\equiv 0\pmod{C}$, $g(y)D-yA\equiv 0\pmod C$, and $0\le f(y),g(y)<C$. They are unique and exist because $\gcd(C,D)=0$. Let $M={}^\lceil\root 3\of{2n}\,{}^\rceil$. By the usual pigeonhole argument, there are $y_1,y_2$ such that $0\le y_1<y_2\le M^2$, $|f(y_1)-f(y_2)|\le M^2$, and $|g(y_1)-g(y_2)|\le M^2$. Now set $$\begin{eqnarray*} x&=&f(y_1)-f(y_2),\\ y&=&y_1-y_2,\\ z&=&g(y_1)-g(y_2).\\ \end{eqnarray*} $$ By Lemma 1 and the definition of $f$ and $g$, it follows that $x,y,z$ are witnesses for $\mu(A,B,C,D)\le\|v(x,y,z)\|_\infty$. By Lemma 2, this implies $$ \mu(A,B,C,D)\le 4\max(|x|,|y|,|z|)\le 4M^2. $$

Theorem 2. There is a constant $L$ such that for $A,B,C,D$ chosen randomly from all possibilities satisfying the assumptions given at the beginning of this answer, the probability of $\mu(A,B,C,D)$ being below a given limit $m$ is less than $Lm^3/n^2$.

Proof. First, fix $C$ and $D$ satisfying the assumptions, and an integer $m>1$. There is a constant $L_1>0$ such that there are at least $L_{1}n^2$ choices for $A,B$. Assume $A,B$ are chosen so that $\mu(A,B,C,D)<m$. Let $x,y,z$ witness this. Then $|x|,|z|<m$. Moreover, $|y|<4m$ by Lemma 2. So, consider $y$ such that $-4m<y<4m$. Let $k=\gcd(y,C)$, and let $y'=y/k,C'=C/k$. For every pair $x',z'$, there are unique $A',B'$ such that $0\le A',B'<C'$ and the following hold: $$ \begin{eqnarray*} x'D+y'B'\equiv 0\pmod {C'},\\ z'D-y'A'\equiv 0\pmod {C'}.\\ \end{eqnarray*} $$ Moreover, for each pair $A',B'$ there are $k^2$ pairs $A,B$ such that $0\le A,B<C$ and $A\equiv A'\pmod {C'}$, $B\equiv B'\pmod {C'}$. There are no more than $2\lceil m/k\rceil$ choices for $x'$ such that $|kx'|<m$. So, for each choice of $y$, there are fewer than $5m^2$ possibilities for the pair $A,B$. Altogether, there are fewer than $10m^3$ choices for $A,B$ such that $\mu(A,B,C,D)<m$, out of at least $L_{1}n^2$. So, we may choose $L=10/L_{1}$.

$\endgroup$
7
  • $\begingroup$ We need a lower bound on probability. Upper bound on probability means nothing. We need something like $P(\mu(A,B,C,D)<m)=\Omega(\frac1{n^\epsilon})$ at any fixed $\epsilon>0$. If that is possible is unclear right? $\endgroup$
    – Turbo
    Commented Mar 6, 2018 at 0:35
  • $\begingroup$ I think I see your intention here. $P(\mu(A,B,C,D)<n^{2/3−\epsilon})<L/n^{2\epsilon}$ from Claim $3.$ and so we have $P(\mu(A,B,C,D)>n^{2/3−\epsilon})>1−L/n^{2\epsilon}$? right? Is that your intention? If so this will be really great. $\endgroup$
    – Turbo
    Commented Mar 6, 2018 at 1:59
  • $\begingroup$ Yes, exactly. I proved your conjecture with an explicit bound on the probability of exceptions. $\endgroup$ Commented Mar 6, 2018 at 7:37
  • $\begingroup$ Does similar probability estimate work for math.stackexchange.com/questions/2456368/…? I look for lower bound there as well. $\endgroup$
    – Turbo
    Commented Mar 6, 2018 at 11:52
  • $\begingroup$ Your other question does look pretty similar, but I can't say quickly if the same technique works. $\endgroup$ Commented Mar 6, 2018 at 12:37
1
$\begingroup$

This is a partial answer in one direction. Let $k=\lceil n/6\rceil$, and let $$A=6k+1, B=10k+1, C=9k+1, D=8k+1. $$ The numbers $A,B,C,D$ are pairwise coprime, larger than $n$, and all their differences are at least $n/6$. It is straightforward to check that $$\pmatrix{\frac{1}{C}&\frac{1}{C}&\frac{3}{C}}N=\pmatrix{-2&1&-2&3}. $$ Moreover, if $n>25$, then $A<D<C<B<2n$. So, for all $n$ large enough, there are $A,B,C,D$ satisfying the given conditions such that $\mu(A,B,C,D)\le 3$.

$\endgroup$
4
  • $\begingroup$ Such choices that you make where you can have gcd of all coordinates very high are exceedingly rare. I still think with high probability lower bound $\Omega(n^{2/3})$ works. $\endgroup$
    – Turbo
    Commented Mar 4, 2018 at 19:16
  • $\begingroup$ That is actually true. I will add a proof. $\endgroup$ Commented Mar 5, 2018 at 13:02
  • $\begingroup$ I meant your conjecture. I don't see any error in my own claim either. $\endgroup$ Commented Mar 5, 2018 at 22:52
  • $\begingroup$ your specific claim is good. $\endgroup$
    – Turbo
    Commented Mar 6, 2018 at 0:34

You must log in to answer this question.