4 ms·
Here's a quite friendly elucidation by the inimitable Avi Wigderson, from: https://www.ias.edu/ideas/2009/wigderson-randomness-pseudorandomness https://www.ias.
by Cybiote 7y ago
Here's a quite friendly elucidation by the inimitable Avi Wigderson, from: https://www.ias.edu/ideas/2009/wigderson-randomness-pseudorandomness https://www.ias.edu/ideas/2009/wigderson-randomness-pseudora...
> Let’s elaborate now on the connection (explained on the cover of this issue) of the Riemann Hypothesis to pseudorandomness. Consider long sequences of the letters L, R, S, such as
> S S R S L L L L L S L R R L S R R R R R S L S L S L L . . .
> Such a sequence can be thought of as a set of instructions (L for Left, R for Right, S for Stay) for a person or robot walking in a straight line. Each time the next instruction moves it one unit of length Left or Right or makes it Stay. If such a sequence is chosen at random (this is sometimes called a random walk or a drunkard’s walk), then the moving object would stay relatively close to the origin with high probability: if the sequence was of n steps, almost surely its distance from the starting point would be close to √n. For the Riemann Hypothesis, the explicit sequence of instructions called the Möbius function is determined as follows for each step t. If t is divisible by any prime more than once then the instruction is Stay (e.g., t=18, which is divisible by 32). Otherwise, if t is divisible by an even number of distinct primes, then the instruction is Right, and if by an odd number of distinct primes, the instruction is Left (e.g., for t=21=3x7 it is Right, and for t=30=2x3x5 it is Left). This explicit sequence of instructions, which is determined by the prime numbers, causes a robot to look drunk, if and only if the Riemann Hypothesis is true!
- j9461701 7y ago>monomer-dimer problem Oh hey, I did my undergrad thesis on that! It generates neat looking graphics: https://imgur.com/a/Z6hySAw https://imgur.com/a/Z6hySAw
- jamiek88 7y agoLooks like an X-ray pic of a system on a chip.
- unixhero 7y agoSomething's going in there.
- teekert 7y agoI did a Masters in Biophysics, the topic was diffusion of proteins in cell membranes, they usually show random walks (albeit restricted to compartments or showing distinct speeds (bound/unbound?)). That graphs does not look like a random walk, so the Riemann Hypothesis is false?
- j9461701 7y agoThe graphic comes from certain assumptions that do not hold in the general case. Specifically, that of non-isotropic fragmentation and arbitrary fragmentation depth.
- wodenokoto 7y ago> (e.g., t=18, which is divisible by 32) Did they mean 3x3x2 instead of 32? There is no way 18 is divisible by 32 in any common sense of divisible. > This explicit sequence of instructions, which is determined by the prime numbers, causes a robot to look drunk, if and only if the Riemann Hypothesis is true! So, do they look drunk for large walks? That sounds like something that is easily computed for tens of thousands of steps.
- emilgouliev 7y agoThey meant 3^2 = 9.
- chii 7y agowhat does "look drunk" actually mean tho? it's a bit of a weird property...
- teekert 7y agoThe drunken man is moving away from where he started (any point in time can be labelled as "start") at a speed of about the square root of his linear speed (speed from his point of view). And the direction is random. This can also be 1D motion. Actually in 1 and 2D it is likely that the drunken man hits his starting point again at some point, it goes to 0 fast in 3D.
- posterboy 7y agoFor 1D It's trivial to see that a side scroller with side-strafing controls (Space Invaders not Asteroids) will always return to the center if L and R appear with equal probability, in euclidean geometry
- wodenokoto 7y agoAs the parent poster quotes, drunk looks like: > if the sequence was of n steps, almost surely its distance from the starting point would be close to √n. Of course that raises the question "What is close?"
- 7y ago