Diophantine approximation via Lattice Reduction

This is all thanks to the LatticeReduce function in Mathematica, which helps us find the closest possible approximation to a given value using the basis vectors of a lattice.
  • #1
Swamp Thing
Insights Author
970
670
With some help from another thread, I learned how to solve a simultaneous diophantine approximation involving log(2), log(3), log(5) etc. This method is based on Mathematica's LatticeReduce function. At first, I was quite happy to use it as a black box to work on some hobby math exploration, but now I would like to understand the solution process a bit more precisely.

To this end I set up a toy problem in Mathematica to find a rational approximation to Log[2]. Take the lattice with basis vectors:
( 1, 0 ) and ( Round(10^6 * log(2)) , 10^6 ).
Make a matrix 'a' whose columns are those vectors. Take b = LatticeReduce[a]. Observe that b(1,1) * log(2) = 642 * log(2) = 445.0004, which is awesome.

But it is not clear to me why this has worked. Here is a diagram showing the original 'a' and the reduced 'b' bases. (One 'a' vector goes off the chart, and one is too small to see, but we'll focus on the reduced bases 'b' which are the blue vectors.

1666504150972.png

From the fact these blue lines are bases of our original lattice, we can say that there are integers M, N such that
##M x_1 + N x_2 = 642 M + 374 N = Round( 10^6 Log(2) )##.

But how does that make 642*log(2) so close to an integer? (It's giving us 445.004, as mentioned above.)

I suspect that the answer may be something utterly trivial that I am missing, but...

===
Edit: minor correction:
##M x_1 + N x_2 = 642 M + 374 N = Round( 10^6 Log(2) )\LARGE\textbf{ +1}##.
(The +1 has a negligible effect on things FAPP, though).
 
Last edited:
Physics news on Phys.org
  • #2
The explanation for why this works is actually quite simple. Since the two blue vectors of the reduced basis 'b' are scaled versions of the original vectors from the lattice, we can assume that the scalar coefficients between them are rational numbers. That is, you can see that ##\frac{x_1}{x_2}## is a rational number.

Then, because the coefficients are rational, the value of ##M x_1 + N x_2## will be close to an integer if the two vectors are close to being multiples of each other. In this case, it turns out that ##M x_1 + N x_2## is almost exactly an integer, which is why we got such a precise result.
 

FAQ: Diophantine approximation via Lattice Reduction

What is Diophantine approximation via Lattice Reduction?

Diophantine approximation via Lattice Reduction is a mathematical method used to find rational approximations to real numbers with a high degree of accuracy. It involves using lattice reduction algorithms to find a basis for a lattice that closely approximates the real number, allowing for efficient computation of rational approximations.

How is Diophantine approximation via Lattice Reduction different from other approximation methods?

Diophantine approximation via Lattice Reduction is unique in that it allows for finding rational approximations to real numbers with a high degree of accuracy. Other approximation methods, such as continued fractions or decimal approximations, may only provide limited accuracy or may not be able to handle certain types of numbers.

What are some applications of Diophantine approximation via Lattice Reduction?

Diophantine approximation via Lattice Reduction has various applications in fields such as cryptography, number theory, and signal processing. It is commonly used to find efficient rational approximations for use in encryption algorithms, as well as in the analysis of number sequences and signal processing algorithms.

What are the limitations of Diophantine approximation via Lattice Reduction?

One limitation of Diophantine approximation via Lattice Reduction is that it can only be applied to real numbers. It also requires a significant amount of computation and may not always provide the most accurate rational approximation. Additionally, it may not be suitable for certain types of numbers with specific properties.

How can Diophantine approximation via Lattice Reduction be implemented in practice?

Diophantine approximation via Lattice Reduction can be implemented through various algorithms, such as the Lenstra-Lenstra-Lovász (LLL) algorithm or the Kannan-Fincke-Pohst (KFP) algorithm. These algorithms can be implemented using programming languages such as Python or Matlab, and can be applied to a wide range of real numbers to find rational approximations with a high degree of accuracy.

Similar threads

Replies
13
Views
2K
Replies
7
Views
1K
Replies
1
Views
1K
Replies
37
Views
3K
Replies
2
Views
1K
Replies
1
Views
2K
Back
Top