I Finding N / log(2) and M / log(3) very close together

[Swamp Thing]

What would be an efficient algorithm for finding pairs of M and N such that $| M/log(2) - N/log(3) |< \delta$ , for some given small $\delta$ ?

Also, such pairs would obviously become scarcer as we reduce $\delta$, but how does it go quantitatively?

 

[fresh_42]

Where are $M,N$ from? How do you define "efficient"? Which computation model do you use?

The best approximation is $\dfrac{M}{\log 2}=\dfrac{N}{\log 3}$ or $\dfrac{M}{N}=\dfrac{\log 2}{\log 3}\approx 0,6309297535714574370995271143427\ldots$

You can choose now $(M/N)\in \left\{\dfrac{6}{10},\dfrac{63}{100},\dfrac{631}{1000},\dfrac{6309}{10000},\ldots\right\}$ which gets as small as you like.

 

[Office_Shredder]

That's not actually obvious to me @fresh_42 . In fact for $|2/9M -N|$ taking $N=22...2$ $n$ twos, and $M=10^n$ yields $|2/9M -N|=2/9$ for all $n$

 

[fresh_42]

That's not actually obvious to me @fresh_42 . In fact for $|2/9M -N|$ taking $N=22...2$ $n$ twos, and $M=10^n$ yields $|2/9M -N|=2/9$ for all $n$

It has been open and unanswered the entire day and I didn't know whether I should solve it, which would have been against the rules, ask for clarification, which I did, expecting a dialogue with the OP, or use a few scribblings with $\dfrac{M}{\log 2}=\dfrac{N}{\log 3}+\varepsilon .$

\begin{align*}
\left|\dfrac{M}{\log 2}-\dfrac{N}{\log 3}\right|&=\varepsilon \\[6pt]
\left|M \log 3 - N \log 2\right|&=\varepsilon \cdot \log 2\cdot \log 3\\[6pt]
\left|\dfrac{M}{N}-\dfrac{\log 2}{\log 3}\right|&=\dfrac{\varepsilon \cdot \log 2 }{N}
\end{align*}
The approximation of $\dfrac{M}{N}$ by $0,6309297535714574370995271143427\ldots$ makes $\varepsilon \cdot \log 2$ arbitrary small for large enough $N$.

Did I make a mistake?

 

[Office_Shredder]

I think so. Maybe there's some special property of log that makes that happen to be true, but the right hand side only goes to zero because N does. If you try to do that procedure with $2/9$ (just picking something easier to compute) at least I found $\epsilon$ to not go to zero as N went to infinity

 

[Swamp Thing]

You can choose now $(M/N)\in \left\{\dfrac{6}{10},\dfrac{63}{100},\dfrac{631}{1000},\dfrac{6309}{10000},\ldots\right\}$ which gets as small as you like.

This may be a silly question, but can we be sure there isn't one between ${\dfrac{631}{1000}}$ and ${\dfrac{6309}{10000}}$ ? This list is based on base 10, but other number bases could give different lists?

How do you define "efficient"?

Loosely, I guess. But I'd like to catch all of the pairs that exist up to a given size of M and N.

I may have posed the question in a non-optimal way, so here is the motivation: We have impulse trains with periods 2 Pi / Log(2) and 2 Pi / Log(3). How can we locate all instances when a pair of pulses, one from each series, gets closer than a given delta?

 

[fresh_42]

I think so. Maybe there's some special property of log that makes that happen to be true, but the right hand side only goes to zero because N does. If you try to do that procedure with $2/9$ (just picking something easier to compute) at least I found $\epsilon$ to not go to zero as N went to infinity

You are right. I must be more careful with $N$ such that it doesn't cancel or lead to a lower bound of $\delta$.

 

[fresh_42]

Yep, it is officially not as trivial as I thought or even trivial at all. We are actually looking for integer values that make the determinant $\left\| \begin{pmatrix}\log 3 &N \\ \log 2 &M \end{pmatrix}\right\|$ or the cell of the corresponding lattice arbitrary small.

I am sure that there is a fancy algorithm for that problem.

Edit: I have found out that there is a solution: Dirichlet 1842 (p.9ff)
https://sites.math.washington.edu/~rothvoss/lecturenotes/IntOpt-and-Lattices.pdf

What a day. From $O(1)$ in the morning to NP-hard at night. It is especially embarrassing since I am 90% sure that I recorded verbal exams about the LLL algorithm many, many years ago.

 

[Swamp Thing]

Thanks... I am trying to understand the Roth-Voss PDF.

After searching for "Mathematica, lattice" I learned that you can use for example, Rationalize[ Log[2] / Log[3], 0.00001] to find fractions that approximate the ratio to within the given delta.

Now, I would also like to find m1 Log[2], m2 Log[3] and m3 Log[5] close together within a given delta. (And so on to include Log[6], Log[7] etc) . Mathematica has a LatticeReduce function. I don't understand it fully, but I'm hoping it can be used to find such points. Can LatticeReduce or some other Mathematica function do this?

 

[Swamp Thing]

I looked at some examples of LatticeReduce and did some trial and error. Finally I could use it for Log[2] and Log[3]:

v = {2 Pi/ Log[2], 2 Pi / Log[3]};
big = Round[10^9 v];
a = {{1, 0, big[[1]]}, {0, 1, big[[2]]}};
b = LatticeReduce[a];{N[b[[1, 1]] 2 Pi /Log[2], 12], N[b[[1, 2]] 2 Pi / Log[3], 12]}
{N[b[[2, 1]] 2 Pi /Log[2], 12], N[b[[2, 2]] 2 Pi /Log[3], 12]}

Output:
{288865.441279, -288865.441219}
{430284.142425, -430284.142515}

So b11, b12 gives me one pair of M, N and b21, b22 gives another pair.

But now when I try it with three logs, I can't figure out how to use the LatticeReduced "b" to get my M1, M2, M3.
I suspect that I have to try multiplying two (or three?) elements of b by each Log thing, but which ones?