Terence Tao's Answer to the Erdős Discrepancy Problem

https://www.quantamagazine.org/20151001-tao-erdos-discrepancy-problem/

by retupmoc01 • 11 years ago

61 23 11 years ago

byron_fast7• 11 years ago

I like Erdos but I have to wonder how much of what he did matters if you look at results in binary instead of Base 10. It seems a lot of number theory seems to gloss over this basic fact. In number theory, it seems Wolfram's four categories explain "impossible problems" pretty simply.

ajkjk• 11 years ago

What are you talking about? What base you write results in has nothing to do with number theory.

monochromatic• 11 years ago

This is not a result that has anything to do with base representation, nor are the vast majority of number theoretic results.

Natsu2• 11 years ago

We're being trolled, I think.

The only thing I can think of where base (sort-of) matters is that we have a formula for the Nth hexadecimal digit of pi, but not for the Nth decimal digit of pi. But I think that's due to lack of interest in making such a function, rather than some inherent reason why this could not be done.

GFK_of_xmaspast• 11 years ago

What does that even mean.

ubernostrum• 11 years ago

Number theory deals with numbers, not the representations of them. The properties of numbers dealt with in number theory exist independently of the base chosen in which to represent the numbers; in fact, a result from number theory (the basis representation theorem) is the formalization of what a "base" actually is and how to represent a number in an arbitrary base.

kenbellows• 11 years ago

Number theory is like the metaphysics of maths. It's metamaths.

byron_fast7• 11 years ago

Your reply is what I always understood about number theory, and is true for many cases. But reading a number of important findings in number theory, when you look at the problem in binary - as Wolfram shows - every problem looks the same.

The unsolvable problems are always noise, the solved problems have a pattern. Like a class 3/4 automata, any unsolved math problem is simply an elaborate way of reaching the same conclusion: randomness, where you can't predict any given value but must compute it.

dogecoinbase• 11 years ago

Would you be willing to elaborate? I'd be curious to hear a specific example of a result due to Erdős that no longer matters in binary, and also a specific impossible problem that's explained by Wolfram (with some detail so I can follow along, of course).

byron_fast7• 11 years ago

Erdos did a lot of work with primes, which if you're searching for patterns looking in binary makes a lot more sense than base 10.

For an example of base-10 centrism that I'm talking about (not specifically Erdos, but from the biography "The Man Who Loved Only Numbers" on page 106 there is a discussion of Stan Ulam writing integers in a spiral and finding primes connected by diagonals. What possible meaning does this pattern have outside of base 10?

This is the part of number theory that confuses me: why should such pattern finding matter, outside of base 10?

byron_fast7• 11 years ago

For an example of using the Wolfram automata-view to look at a problem, think of Fermat's Last Theorem. Can a specific cube (or any higher power, really) be expressed as the sum of two other cubes?

The automata view shows us the answer because when you look at the list of cubes (or any higher power) as binary the resulting image meets the Wolfram test for randomness. Looking at these numbers in any other base has no obvious meaning, but in binary you can instantly see whether some set at least looks like a random automata.

When I look at number theory or indeed any insoluble math problem it always seems to be some variation on people trying to write an equation that satisfies something from a random automata.

Essentially all unsolved problems boil down to an argument about whether you believe automata show randomness or not.

axiak• 11 years ago

Here's a link to the paper: http://lanl.arxiv.org/pdf/1509.05363.pdf

Natsu2• 11 years ago

There was more discussion on a previous HN submission regarding this discovery, as well:

https://news.ycombinator.com/item?id=10282230

The original Nature article had some very good background, including a link to the blog comment that gave Tao the impetus to explore a connection that led to this discovery (and which Tao credited in the paper):

http://www.nature.com/news/maths-whizz-solves-a-master-s-rid...

Sniffnoy• 11 years ago

A note -- if you're linking to arXiv, it's better to link to the abstract (http://arxiv.org/abs/1509.05363) rather than directly to the PDF. From the abstract, one can easily click through to the PDF; not so the reverse. And the abstract allows one to do things like see different versions of the paper, search for other things by the same authors, etc. Thank you!

Terence Tao's Answer to the Erdős Discrepancy Problem

Related Stories