# Size of approximate solution of an integer relation

Let $X_1$, ..., $X_n$ be a list of real numbers.

Consider an integer relation equation

$A_1 X_1 + \ldots + A_n X_n = 0$

where $A_1$, ..., $A_n$ are unknown integers.

Suppose somehow we are not so much interested in exact solution of the relation as we are interested in making the $|A_1 X_1 + \ldots + A_n X_n|$ as small as possible.

Question 1: what is an upper bound (in terms of $\epsilon$) on the norm $|[A_1,\ldots,A_n]|$ for which $|A_1 X_1 + \ldots + A_n X_n| < \epsilon$ ?

0) Vector $X_1$, ..., $X_n$ is assumed to be in general position

1) it is ok to assume that $|[X_1,...,X_n]|=1$

2) I will be happy to learn an answer in the specific context of the PSLQ algorithm

3) and/or I will be happy to know the answer for $n=4$

4) if this helps...

Question 2: What would be some general method(s) to investigate Question 1?

Alex--

• Isn't this just the multidimensional generalization of Dirichlet's Theorem on Diophantine Approximation? – Gerry Myerson Mar 31 '14 at 22:05
• It looks like you can frame it like this, but it does not really help me :-) Unless that generalization of Dirichlet is written up somewhere... – Alex Mar 31 '14 at 22:18
• It's written up in many places. I suspect you could find a few by asking Google about $$\rm Dirichlet\ diophantine\ approximation$$ – Gerry Myerson Mar 31 '14 at 22:20
• Hmmm... The best I could find were tutorials on simultaneous Diophantine approximations. This is an entirely different animal. Even if you manage to piece together an integer relation from the simultaneous Dirichlet, its quality is going to be quite bad. – Alex Mar 31 '14 at 22:58

Theorem 1C of Schmidt's book, Diophantine Approximation, says if $\alpha_1,\dots,\alpha_n$ are real and $Q>1$ is an integer then there exist integers $q_1,\dots,q_n$ and $p$ such that $$1\le\max(|q_1|,\dots,|q_n|)<Q^{1/n}{\rm\ and\ }|\alpha_1q_1+\cdots+\alpha_nq_n-p|\le Q^{-1}$$ Given your list $X_1,\dots,X_n$ of real numbers, assume $X_n\ne0$, and let $\alpha_i=X_i/X_n$ for $1\le i\le n-1$. The theorem gives you integers $q_1,\dots,q_{n-1}$ and $p$ such that $|\alpha_1q_1+\cdots+\alpha_{n-1}q_{n-1}-p|$ is small, and then multiplying by $X_n$ you get a result on $|q_1X_1+\cdots+q_{n-1}X_{n-1}-pX_n|$.