🔖 The Entropy Decrement Method and the Erdos Discrepancy Problem | Simons Institute for the Theory of Computing

Bookmarked The Entropy Decrement Method and the Erdos Discrepancy Problem (Simons Institute for the Theory of Computing)

Tuesday, April 11th, 2017 9:30 am – 10:30 am
Structure vs. Randomness
Speaker: Terry Tao, UCLA

We discuss a variant of the density and energy increment arguments that we call an "entropy decrement method", which can be used to locate a scale in which two relevant random variables share very little mutual information, and thus behave somewhat like independent random variables.  We were able to use this method to obtain a new correlation estimate for multiplicative functions, which in turn was used to establish the Erdos discrepancy conjecture that any sequence taking values in {-1,+1} had unbounded sums on homogeneous arithmetic progressions.

Syndicated copies to:

🔖 [1509.05363] The Erdos discrepancy problem by Terence Tao | arXiv

Bookmarked [1509.05363] The Erdos discrepancy problem by Terence TaoTerence Tao (arxiv.org)

We show that for any sequence f:N→{−1,+1} taking values in {−1,+1}, the discrepancy
supn,d∈N∣∣∣∣∑j=1nf(jd)∣∣∣∣
of f is infinite. This answers a question of Erdős. In fact the argument also applies to sequences f taking values in the unit sphere of a real or complex Hilbert space. The argument uses three ingredients. The first is a Fourier-analytic reduction, obtained as part of the Polymath5 project on this problem, which reduces the problem to the case when f is replaced by a (stochastic) completely multiplicative function g. The second is a logarithmically averaged version of the Elliott conjecture, established recently by the author, which effectively reduces to the case when g usually pretends to be a modulated Dirichlet character. The final ingredient is (an extension of) a further argument obtained by the Polymath5 project which shows unbounded discrepancy in this case.

Syndicated copies to:

🔖 Sign patterns of the Mobius and Liouville functions | Terence Tao

Bookmarked Sign patterns of the Mobius and Liouville functions by Terence Tao (What's new)
Kaisa Matomäki, Maksym Radziwiłł, and I have just uploaded to the arXiv our paper “Sign patterns of the Liouville and Möbius functions”. This paper is somewhat similar to our previous p…
Syndicated copies to:

🔖 [1501.04585] Multiplicative functions in short intervals | arXiv

Bookmarked [1501.04585] Multiplicative functions in short intervals by Kaisa Matomäki, Maksym Radziwiłł (arxiv.org)
We introduce a general result relating "short averages" of a multiplicative function to "long averages" which are well understood. This result has several consequences. First, for the M\"obius function we show that there are cancellations in the sum of μ(n) in almost all intervals of the form [x,x+ψ(x)] with ψ(x)→∞ arbitrarily slowly. This goes beyond what was previously known conditionally on the Density Hypothesis or the stronger Riemann Hypothesis. Second, we settle the long-standing conjecture on the existence of xϵ-smooth numbers in intervals of the form [x,x+c(ε)x−−√], recovering unconditionally a conditional (on the Riemann Hypothesis) result of Soundararajan. Third, we show that the mean-value of λ(n)λ(n+1), with λ(n) Liouville's function, is non-trivially bounded in absolute value by 1−δ for some δ>0. This settles an old folklore conjecture and constitutes progress towards Chowla's conjecture. Fourth, we show that a (general) real-valued multiplicative function f has a positive proportion of sign changes if and only if f is negative on at least one integer and non-zero on a positive proportion of the integers. This improves on many previous works, and is new already in the case of the M\"obius function. We also obtain some additional results on smooth numbers in almost all intervals, and sign changes of multiplicative functions in all intervals of square-root length.
Syndicated copies to:

👓 Terence Tao’s Answer to the Erdős Discrepancy Problem | Quanta Magazine

Read Terence Tao's Answer to the Erdős Discrepancy Problem by Erica KlarreichErica Klarreich (Quanta Magazine)
Using crowd-sourced and traditional mathematics research, Terence Tao has devised a solution to a long-standing problem posed by the legendary Paul Erdős.

In the middle of the lecture last night, I was thinking to myself that this problem seems like a mixture of combinatorics, integer partitions and coding theory. Something about this article reminds me of that fact again. Most of the references I’m seeing however are directly to number theory and don’t relate to the integer partition piece–perhaps worth delving into to see what shakes out.

The article does a reasonable job of laying out some of the problem and Tao’s solution to it. I was a bit bothered by the idea of “magical” in the title, but it turns out it’s a different reference than the one I was expecting.

Syndicated copies to:

Gems And Astonishments of Mathematics: Past and Present—Lecture One

Last night was the first lecture of Dr. Miller’s Gems And Astonishments of Mathematics: Past and Present class at UCLA Extension. There are a good 15 or so people in the class, so there’s still room (and time) to register if you’re interested. While Dr. Miller typically lectures on one broad topic for a quarter (or sometimes two) in which the treatment continually builds heavy complexity over time, this class will cover 1-2 much smaller particular mathematical problems each week. Thus week 11 won’t rely on knowing all the material from the prior weeks, which may make things easier for some who are overly busy. If you have the time on Tuesday nights and are interested in math or love solving problems, this is an excellent class to consider. If you’re unsure, stop by one of the first lectures on Tuesday nights from 7-10 to check them out before registering.

Lecture notes

For those who may have missed last night’s first lecture, I’m linking to a Livescribe PDF document which includes the written notes as well as the accompanying audio from the lecture. If you view it in Acrobat Reader version X (or higher), you should be able to access the audio portion of the lecture and experience it in real time almost as if you had been present in person. (Instructions for using Livescribe PDF documents.)

We’ve covered the following topics:

  • Class Introduction
  • Erdős Discrepancy Problem
    • n-cubes
    • Hilbert’s Cube Lemma (1892)
    • Schur (1916)
    • Van der Waerden (1927)
  • Sylvester’s Line Problem (partial coverage to be finished in the next lecture)
    • Ramsey Theory
    • Erdős (1943)
    • Gallai (1944)
    • Steinberg’s alternate (1944)
    • DeBruijn and Erdős (1948)
    • Motzkin (1951)
    • Dirac (1951)
    • Kelly & Moser (1958)
    • Tao-Green Proof
  • Homework 1 (homeworks are generally not graded)

Over the coming days and months, I’ll likely bookmark some related papers and research on these and other topics in the class using the class identifier MATHX451.44 as a tag in addition to topic specific tags.

Course Description

Mathematics has evolved over the centuries not only by building on the work of past generations, but also through unforeseen discoveries or conjectures that continue to tantalize, bewilder, and engage academics and the public alike. This course, the first in a two-quarter sequence, is a survey of about two dozen problems—some dating back 400 years, but all readily stated and understood—that either remain unsolved or have been settled in fairly recent times. Each of them, aside from presenting its own intrigue, has led to the development of novel mathematical approaches to problem solving. Topics to be discussed include (Google away!): Conway’s Look and Say Sequences, Kepler’s Conjecture, Szilassi’s Polyhedron, the ABC Conjecture, Benford’s Law, Hadamard’s Conjecture, Parrondo’s Paradox, and the Collatz Conjecture. The course should appeal to devotees of mathematical reasoning and those wishing to keep abreast of recent and continuing mathematical developments.

Suggested Prerequisites

Some exposure to advanced mathematical methods, particularly those pertaining to number theory and matrix theory. Most in the class are taking the course for “fun” and the enjoyment of learning, so there is a huge breadth of mathematical abilities represented–don’t not take the course because you feel you’ll get lost.

Register now

I’ve written some general thoughts, hints, and tips on these courses in the past.

Renovated Classrooms

I’d complained to the UCLA administration before about how dirty the windows were in the Math Sciences Building, but they went even further than I expected in fixing the problem. Not only did they clean the windows they put in new flooring, brand new modern chairs, wood paneling on the walls, new projection, and new white boards! I particularly love the new swivel chairs, and it’s nice to have such a lovely new environment in which to study math.

The newly renovated classroom space in UCLA’s Math Sciences Building

Category Theory for Winter 2019

As I mentioned the other day, Dr. Miller has also announced (and reiterated last night) that he’ll be teaching a course on the topic of Category Theory for the Winter quarter coming up. Thus if you’re interested in abstract mathematics or areas of computer programming that use it, start getting ready!

Syndicated copies to:

👓 On the recently removed paper from the New York Journal of Mathematics | Terence Tao

Read On the recently removed paper from the New York Journal of Mathematics by Terence Tao (What's new)
In the last week or so there has been some discussion on the internet about a paper (initially authored by Hill and Tabachnikov) that was initially accepted for publication in the Mathematical Inte…

I wish there were more on the math here or at least some solid discussion of the actual science. The huge number of comments make me just think that this is gasoline, however well intentioned it may be.

Syndicated copies to:

👓 Riemann hypothesis, fine structure constant, Todd function | John D. Cook

Read Riemann hypothesis, fine structure constant, Todd function by John D. Cook (johndcook.com)
This morning Sir Michael Atiyah gave a presentation at the Heidelberg Laureate Forum with a claimed proof of the Riemann hypothesis. The Riemann hypothesis (RH) is the most famous open problem in mathematics, and yet Atiyah claims to have a simple proof.

Based on the update that the whole thing may fall apart, but the fact that it’s based on the Todd function as it reaches a limit for the fine structure constant might provide an answer to Sean Carroll’s issues? We’ll see what comes of it.

Syndicated copies to:

As I get amped up for the start of Mike Miller’s Fall math class Gems and Astonishments of Mathematics, which is still open for registration, I’m even more excited that he’s emailed me to say that he’ll be teaching Category Theory for the Winter Quarter in 2019!!

 

 

Syndicated copies to:

👓 Riemann hypothesis likely remains unsolved despite claimed proof | New Scientist

Read Riemann hypothesis likely remains unsolved despite claimed proof by Gilead Amit​ (New Scientist)
Mathematician Michael Atiyah has presented his claimed proof of one of the most famous unsolved problems in maths, but others remain cautiously sceptical
Syndicated copies to:

👓 Atiyah and the Fine-Structure Constant | Sean Carroll

Read Atiyah and the Fine-Structure Constant by Sean Carroll (Sean Carroll)
Sir Michael Atiyah, one of the world’s greatest living mathematicians, has proposed a derivation of α, the fine-structure constant of quantum electrodynamics. A preprint is here. The math her…
Syndicated copies to:

🔖 Categorical informatics

Bookmarked Categorical informatics by David Spivak (math.mit.edu)

"Category theory is a universal modeling language."

Background.

Success is founded on information. A tight connection between success (in anything) and information. It follows that we should (if we want to be more successful) study what information is.

Grant proposals. These are several grant proposals, some funded, some in the pipeline, others not funded, that explain various facets of my research project.

Introductory talk (video, slides).

Blog post, on John Baez's blog Azimuth, about my motivations for studying this subject. (Here's a .pdf version.)

Syndicated copies to:

👓 News re proofs of the ABC conjecture & Riemann Hypothesis | John D. Cook

Read News re proofs of the ABC conjecture & Riemann Hypothesis by John D. Cook (johndcook.com)
There have been a couple news stories regarding proofs of major theorems. First, an update on Shinichi Mochizuki’s proof of the abc conjecture, then an announcement that Sir Michael Atiyah claims to have proven the Riemann hypothesis.
Syndicated copies to:

👓 Famed mathematician claims proof of 160-year-old Riemann hypothesis | New Scientist

Read Famed mathematician claims proof of 160-year-old Riemann hypothesis by Gilead Amit​ (New Scientist)
Michael Atiyah, a famed UK mathematician, claims that he has a "simple proof" of the Riemann hypothesis, a key unsolved question about the nature of prime numbers
Syndicated copies to: