- #1

- 709

- 240

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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- I
- Thread starter Swamp Thing
- Start date

- #1

- 709

- 240

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

- #2

- 17,643

- 18,283

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.

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.

Last edited:

- #3

Office_Shredder

Staff Emeritus

Science Advisor

Gold Member

- 5,456

- 1,387

- #4

- 17,643

- 18,283

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?

- #5

Office_Shredder

Staff Emeritus

Science Advisor

Gold Member

- 5,456

- 1,387

- #6

- 709

- 240

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?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.

Loosely, I guess. But I'd like to catch all of the pairs that exist up to a given size of M and N.How do you define "efficient"?

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?

- #7

- 17,643

- 18,283

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

Last edited:

- #8

- 17,643

- 18,283

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.

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.

Last edited:

- #9

- 709

- 240

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?

- #10

- 709

- 240

Code:

```
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}
```

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?

Share:

- Replies
- 1

- Views
- 459

- Last Post

- Replies
- 13

- Views
- 864

- Replies
- 44

- Views
- 2K

- Last Post

- Replies
- 10

- Views
- 800

- Last Post

- Replies
- 1

- Views
- 441

- Replies
- 10

- Views
- 524

- Last Post

- Replies
- 4

- Views
- 1K

- Last Post
- Math POTW for Graduate Students

- Replies
- 6

- Views
- 457

- Last Post

- Replies
- 4

- Views
- 838

- Last Post

- Replies
- 4

- Views
- 420