joshuazelinsky | Entries tagged with number theory

New preprint of a paper with Tim McCormack is up https://arxiv.org/abs/2312.11661 ! Let's talk about it!

Everyone knows how to calculate the average, or arithmetic mean of a list of numbers. You add them all up and then divide by the number of things on the list. So, if you want the average of 3, 9, and 27, you add them up to get (3+9+27)/3= 13. But this is not the only sort of average you can take of a list of numbers . Another notion of average in the sense of something which represents a typical value is the geometric mean, where one multiplies all the numbers together and then takes the nth root where n is the number of items on the list. So in our case we would take (3*9*27)^(1/3) = 9. (To make sure this makes sense, we need to insist that our numbers chosen are always positive.)

Essentially, the arithmetic mean is asking to find a number m such that if you add m up n times, one gets the same result as the sum of the numbers on the list. The geometric mean is asking to find a number where when one multiplies that number by itself m times one gets the same number as the product of the numbers on the list. In our example, 13+13+13= 3+9+27, and 9*9*9= 3*9*27.

Now, one thing you may notice is that 9 is less than 13. In fact, this always happens and the arithmetic mean is always greater than the geometric mean, with the exception when all the numbers on your list are equal. This is known as the arithmetic-mean-geometric mean inequality, or the AM-GM inequality.

A brief digression: Oyestein Ore was a mathematician who among other things was the doctoral supervisor for Grace Hopper, and also was the writer of "Number Theory and Its History" which in my opinion remains the best introduction to number theory for people with no background. (My own biases come in part from having read it in 8th and 9th grade and it contributing to my own long-term research interests.) Ore was interested in understanding the positive divisors of numbers. One thing he did is looked at the geometric mean of a set of the positive divisors of a number, which we will call G(n). For example, 10 has divisors 1,2,5 and 10. And so the geometric mean of the divisors is (1*2*5*10)^(1/4)= 100^(1/4) = √10. In fact, Ore was able to show that the geometric mean of the divisors of a number is always the square root of the number. This is a fun exercise if you have not seen it before. (Hint: Try to pair the divisors up that multiply to n. So in our example above 1 pairs with 10 while 2 pairs with 5.)

Note that if write tau(n) as the number of positive divisors of n, and sigma(n) as the sum of the divisors of n. (So for example, tau(10)=4, and sigma(10)=1+2+5+10=18.) Then the average of the divisors is sigma(n)/tau(n). Ore combined this observation with the AM-GM inequality conclude that one must therefore have √n < sigma(n)/tau(n). However, this inequality is essentially trivial, since it is the same as tau(n)√n < sigma(n), and it turns out that for large n, tau(n) is very small compared to n, and obviously sigma(n) is in general bigger than n.

And to some extent this should not be surprising: the AM-GM inequality is a statement about all real numbers. It cannot "know" much of anything about collections of divisors since it is only taking into account them being a list of real numbers. However, there is another version of the AM-GM inequality, the weighted AM-GM which allows one to take averages where some numbers on your list "weigh" more than others. The analogy that may help here is that this is essentially how you take an average when you have multiple grades that count a different amount, and so each is weighed accordingly. So the question arises: can one use the weighted version of the AM-GM inequality with suitably chosen weights to get interesting number theoretic inequalities?

This paper by Tim McCormack and me addresses this question. We show that the answer is yes, but but only weakly. But along the way, we prove a bunch of new inequalities, about Zaremba's function among other things. Zaremba's function, z(n), is the sum of (ln d)/d where d ranges over the divisors of n. So for example, z(4)= (ln 1)/1 + (ln 2)/2 + (ln 4)/4 .

One fun thing that this is connected to is a class of pseudoperfect numbers that we prove new things about. Recall a number is said to be perfect if when we add up all the divisors less than the number we get the number Equivalently when we add up all the divisors we get twice the number. For example, 6 is perfect because 1+2+3=6, or equivalently, 1+2+3+6=12=2(6). A number n is said to be pseudoperfect if when you add some subset of the divisors you get twice the number. For example, 12 is not perfect, because all its divisors add up to too much: 1+2+3+4+6+12=28. But if we are allowed to forget about 4, then it looks perfect: 1+2+3+6+12=24. So pseudoperfect numbers are numbers where we are allowed to cheat. However, pseudoperfect numbers are in some sense way too common. Lots of numbers are pseudoperfect. But we can restrict things a bit, to insist that our divisors look a lot like an actual set of divisors for a number could be using the same pairing rule we used to prove that the geometric mean of the divisors of n is √n . We'll say that a number n is strongly pseudoperfect if there is a subset S of its divisors which add up to 2n and where a given divisor d is in S if and only if n/d is in S. For example, 12 would fail to be pseudoperfect above, because we dropped 4, but 4/12=3 is in our set S. In contrast, 36 is strongly pseudoperfect because we could take the set 1 +2+3 +12+18+36=2(36). We prove that strongly pseudoperfect numbers satisfy some interesting behavior, including that they end up looking a lot closer to perfect numbers than general pseudoperfect numbers.

Strongly pseudoperfect numbers are much rarer than general pseudoperfect numbers. Whenever a number n is pseudoperfect, mn is pseudoperfect for any m. This is another good exercise. However, this is not the case for strongly pseudoperfect numbers. In particular, if n is strongly pseudoperfect and p is a sufficiently large prime, then pn is not strongly pseudoperfect.

We don't know that much about strongly pseudoperfect numbers. There are no strongly pseudoperfect n numbers which are 2 mod 3 (that is where n leaves a remainder of 2 when divided by 3), and there are also no strongly pseuoperfect numbers which are 3 mod 4. Are these the only mod restrictions on strongly pseudoperfect numbers or are there others?

Also, 60, 120, 240, 480, 960 are all strongly pseudoperfect. Does this pattern continue indefinitely?

Today was mathematician Srinivasa Ramanujan's birthday. A lot of people have heard of him (especially in the context of the 1729 story). I want to talk about a different result of his, and then ask a related question.
A partition of a natural number is a way of writing a natural number as the sum of a bunch of numbers where we do not care about the order of the sum. For example, 8 = 4 + 2 + 2 gives a partition of 8, and we regard 2 + 4 +2 and 2 + 2 + 4 as the same partition. (Exercise: Find all the partitions of 5. You should find 7 of them.) Ramanujan studied the number of partitions of a given number n, which we write as p(n).

Ramanujan noticed, and proved an intriguing pattern about partitions. In particular, he proved that if you have a number n which leaves a remainder of 4 when divided by 5, then p(n) is divisible by 5. For example, p(4) = 5, and p(9) = 30.) Since that discovery, Ramanujan and then other people went gone on to prove similar relationships with other numbers other than 5. For example, Ramanujan proved that p(7t + 5) leaves a remainder of 0 when divided by 7. Frustratingly, we don't have any similar results for 2 or 3 although we have similar results for other primes. We can't even prove that there are infinitely many n where p(n) is even.

Another aspect where Ramanujan worked on the partition function was approximating p(n). When a function grows, mathematicians like to estimate its growth rate. For example, there's a famous result that the nth prime number for large n is very close to n ln n . Ramanujan with G. H. Hardy proved a result that says that essentially p(n) grows roughly like an exponential to a square root of n.

This is weird. Growth rates don't normally look like that. To some extent though, the partition function is forced to have a weird growth rate because it must have a growth faster than any polynomial but slower than any exponential. To see why it has to grow faster than polynomial think about the function p(k,n) which looks at how many partitions n has into numbers which are at most k. Note that p(1, n) = 1, since, the only way to write n as a sum of 1s is to just write n = 1 + 1 +1 ... +1. But, now, p(2,n) will grow roughly like n/2, because we have p(2,n) = p(1,n) + p(1, n-2) + p(1, n-(2+2)) ... . Similarly, then p(3,n) will grow quadratically, like a constant times n^2, since p(3,n) = p(2, n) + p(2,n-3) + p(2, n - (3+3+3))... In general then p(k,n) will grow roughly like n^(k-1).

Here's my question then: Is there any similarly straightforward and simple proof that p(n) grows slower than any exponential? It is trivially bounded above by 2^n, since the number of ways of breaking n down into a sum where we do care about the order is 2^n. However, I don't know of a similarly simple argument that it has to grow slower than any exponential. There's a not too difficult proof in Apostol's "Introduction to Analytic Number Theory" that shows that the growth is at most roughly the correct growth rate, but that involves using generating functions and then doing calculus on the generating functions. I'm hoping for some simple combinatorial argument here.

This is a new paper I coauthored with Sean Bibby and Pieter Vyncke. We prove new things about large prime factors of odd perfect numbers. The paper is pretty readable if one has only a very small amount of number theory background.

Recall that a number is perfect if the sum of its divisors less than the number is equal to the number. For example, 6 is perfect since the relevant divisors are 1, 2 and 3, and 1+2+3=6. One of the oldest unsolved problems in all of math is whether there are any odd numbers which are perfect.
In the last few years, there's been a bit of work on bounds about the largest prime factors of an odd perfect number N. In particular, assume that the the distinct prime factors of N are p1, p2, p3 ... pk with p1 < p2 < p3 ... < pk .
Acquaah and Konyagin proved that one must have pk < (3N)^(1/3) . Subsequently, using essentially the same techniques as them proved that p(k-1) < (2N)^(1/5), and that p(k-1)pk < 3N^(1/2). In a similar vein Luca and Pomerance using a similar technique showed that p1p2p3... pk < 2N^(17/26). In this paper , we prove that p(k-2) < (2N)^(1/6), and that p(k-2)p(k-1)pk < (2N)^(3/5). Note that 17/26 > 3/5, so this is an actual improvement over Luca and Pomerance's bound, although at the cost of only applying to the product three largest distinct prime factors rather than the product of all of them.

Highly composite numbers are numbers whose total number of divisors is greater than any smaller number. For example, 12 has 6 divisors, 1, 2, 3, 4, 6 and 12, and no number smaller than 12 has 6 or more divisors. There's a really good video on them here .

These were first studied by Ramanujan a little over a hundred years ago. He proved a bunch of statements about them, some of the easier ones of which are included in the video above with proofs. Here are two of those: First, If N is a highly composite number and we list its distinct prime factors in order, then we cannot skip any prime factor. For example, 66 cannot be a highly composite number because 66=2*3*11 and so we skipped 5 and 7. Second, if N is a highly composite number, we cannot have an exponent of a prime in the factorization be higher than the exponent for a smaller prime. For example, 150 cannot be highly composite because 150 = 2^1 * 3^1 * 5^2 and 2>1.

Now, I want to mention something not in the above video that was pretty surprising to me the first time I learned about it: If we list the number of distinct prime divisors each highly composite number has, we might expect that number to never go down. (By number of distinct prime divisors we mean that we count primes which repeat in the factorization only once. So for example, 150 above would have three distinct prime factors.) And for the first few this is true, as you can check. But it does break down! 27720 is a highly composite numbers. We have 27720 = 2^3 * 3^2 * 5 * 7 * 11 with 5 distinct prime divisors, and a total of 96 total divisors. But the next highly composite number is 45360 = 2^4 * 3^4 * 5 * 7 is the next highly composite number. 45360 has only 4 distinct prime divisors; notice we lost the 11. There are even larger examples where we lose two prime factors when going up. I don't know of any example where we lose 3 or more, and as far as I'm aware whether there are any is an open question.

Define a function f(x) which takes a number and adds to that number the sum of its digits in base 10. For example, f(112) = 116 because 116 = 112+1+1+2. We can keep applying this function to itself and get a sequence. For example, if we started with 7, we would get 7, 14, 19, 29, 40, 44, 52, 59... and so on.

We'll call such a sequence a river. One thing to note is that some river can start off with one number and eventually turn into another river. For example, 3,6, 12, 15, 21, 24, 48, 60, 66, 78, 93, 105, 111, 114, and 30, 33, 39, 51, 57, 69, 84, 96, 111, 114... If two rivers meet, they are then the same at any subsequence point.

Rivers are related to self-numbers which are numbers which are not in the range of f(x). They can be thought of as numbers which only ever appear at the start of a river, never in the middle.

I was introduced to the idea of rivers by this Mathoverflow question . They define three "main rivers" , 1, 2, 4, 8, 16, 23..., 3,6, 12, 15, 21..., and 9, 18, 27,... and prove that these three can never intersect (this is a good exercise!) . They ask if every river eventually meets one of these three main rivers.

However, it isn't obvious to me that there is even a finite set of rivers such that any river eventually meets one of those. So, let's do what mathematicians always do when we can't answer a question, try to ask a related question. We can define rivers the same way for any base b, where our function f_b(x) adds x to the sum of the base b digits. It isn't obvious to me how to even prove that there is any base b where there's a finite collection of rivers which are always eventually met. A small amount of playing around suggests that in base 3, every river eventually meets the river started by 1, but I don't see any obvious way to prove it.

An infamously difficult unsolved problem in mathematics is to prove that factoring numbers is tough. We know that if someone gives you a claimed factorization that it is easy to check. If someone asks you to factor 629, you may not have an easy time. But if someone tells you that 629 is 17 times 37, you can check this by hand (or if you want even more easily with a calculator). In general, proving that something is tough to do is very hard. Even after one gets past all the issues of how to define what one means rigorously, one has to somehow prove that *no algorithm* works efficiently and that's a tall order. But in the case of factoring there are some interesting examples of how far we are from actually proving anything which are worth stating explicitly.

Here's a naive way of trying to factor a number (discussed in more detail at this excellent Quanta article ). The basic idea is that it turns out that polynomials (assuming their degree and coefficients aren't too large) are easier to factor than numbers. How can we take advantage of that? Let's say we wanted to factor the number 15, and we didn't notice it was just 15 = (3)(5). So instead we'll try to write 15 in base 2, where we get 15 = 1111₂, and this is the same as saying 15 = 1(2³)+1(2²)+1(2)+1, and this now is almost a polynomial, in particular it is the value of the polynomial x³ +x² +x +1 when x=2. So if we can factor x³ +x² +x +1. we can use that to factor our original. Sure enough, x³ +x² +x + 1 = (x+1)(x²+1), and so we plug back in x=2, and we get that 15 = (2+1)(2²+1) = (3)(5). We did this using base 2, but one can use the same trick in other bases for some numbers. (Of course it could turn out that n is prime in which case this trick will fail for any base, but we can detect primes using other means so that's ok.) Maybe this trick will almost always work. We don't get that lucky, but even proving this is tough. Emmanuel Breuillard and Péter Varjú proved that (assuming the Riemann Hypothesis), that for any base b, only a very tiny fraction of numbers can be factored using this trick. But wait, you say, that just means we probably can't do this for a specific base. What if we're allowed to pick our base cleverly. Maybe we can always find such a base if we can somehow choose the base. Or maybe, we can go through a small list of bases, say try this trick with every base b where b is small compared to n, say not much bigger than log log n. Already we can't prove that this doesn't work, although it does seem plausible that the techniques of Breuillard and Varjú could be extended to this context, and Theorem 2 from their paper does push in that direction. But if we struggle to even prove that this sort of very basic (if you'll pardon the pun) trick won't work in general, how can we possibly hope to prove that factoring itself is tough? Worse, from a security standpoint, the numbers we really care about not being able to factor efficiently are *semiprimes* that is a number which is a product of exactly two primes. 15 above is an example of a semiprime, but for example, 1001 is not a semiprime because it had three prime factors, 1001=(7)(11)(13).

In fact, most positive integers are easy to factor; the difficulty is really showing that numbers which are not prime but have only a small set of prime factors each of which is relatively large compared to the number are difficult to factor. Here's another example although in some respects a bit sillier. It also turns out that there's an easy way given two positive integers x and y to find their greatest common divisor which is much more efficient than factoring x and y . For example, it may not be that easy to factor 133 or 217, but if you can find their gcd, which is 7, then you've already found a factor for both. The ability to efficiently find gcds is due to the Euclidean Algorithm and has been known for about 2000 years. So, maybe we can given a number n, make a short list of numbers based on n, and get that the gcd of n and at least one of these numbers is greater than 1, in which case we've found a factor. So, in that spirit, here's a naive idea which has absolutely no serious hope of actually working but which I don't know how to prove that it doesn't work: For a given positive integer we can look at its digital reversal in base b, which we can get when we take the number where we write all its digits in base b in reverse. For example, in base 10, 132 would become 231. Maybe, for n, we can find a small base b, such that n and the digital reversal of n share a common factor. This isn't interesting with our example of 15, since 15 in base 2 is just 1111₂ so it is the same as its digital reversal. But this does actually work to factor some numbers and bases. For example, 21 in base 10 has a digital reversal of 12, and 21 and 12 share a common factor of 3. In fact, a good exercise is to show that if n is divisible by 3, then n does share a factor of 3 with its base 10 digital reversal (what is the correct generalization here to any given base?). So here's a statement which must be false but I don't know how to prove: Given a composite n, there's always a base b where b is small compared to n (say not larger than a constant time log n) and n and the digital reversal of n with respect to b has a common prime factor. It may be that there's an easy proof that the above doesn't happen, but if so, I don't know of it. Now, a professional, either a number theorist or a computer scientist, might object to some of what we've written above: Of course, proving these sorts of things is difficult. Proving statements about the behavior of numbers in different bases is known in general to be very difficult. (For one semi-famous unsolved problem of this sort: We strongly suspect that this sequence is finite https://oeis.org/A258107 but cannot prove it. ) So why should we be surprised that these sorts of things are tough to prove? But this underscores exactly why proving that factoring is hard; if we can't even prove things about these highly restricted algorithms coming just from writing the number in various bases, how can we hope to prove anything when the space of all possible algorithms is far, far larger?

Most people have at this point probably heard of the Fibonacci sequence. (Fibonacci actually never went by that name but that's a whole other story.) This sequences goes 1,1,2,3,5,8,13,21,34,55,89...

Each term is made from the sum of the previous two terms.  For example, 3+5=8, and then 5+8=13. But since almost everyone has heard of this sequence, it can be a bit boring. So let us spice it up slightly. We could use the same rule for making new terms, but start with any two natural numbers. For example, we could do the sequence 1, 3, 4, 7, 11, 18, 29, 47... Here we started with 1 and 3. Or we could choose some other starting value, say 2 and 2 to get 2, 2, 4, 6, 10, 16, 26... Note that this last sequence isn't very interesting; each term is just twice the corresponding term in the Fibonacci sequence; we could write it as 2(1), 2(1), 2(2), 2(3), 2(5), 2(8), 2(13) and so on. We'll call any sequence which starts with two natural numbers and then makes each new term using the Fibonacci rule Fibonacci-like. 

One famous open problem about the Fibonacci sequence is if there are infinitely many Fibonacci numbers which are prime. That is, are there infinitely many numbers like 2, 3, 5, and 13. (7 is prime but not Fibonacci. 8 is Fibonacci but not prime.)  We strongly believe the answer is yes.  Right now, the largest known Fibonacci prime is F_104911. That is, the 104911th Fibonacci number is prime. 

One might note that for small n it seems like F_n is prime if and only if n is prime. This turns out not to be the case. It turns out that if the nth Fibonacci number is prime then one needs that n is prime. But the other direction does not hold.  For example, the 19th Fibonacci number, F_19, is 4181 which is 37 times 113. 

Since we already had a game where we make Fibonacci-like sequences, and trying to figure out where there are infinitely many Fibonacci primes seems hard, maybe we can look at these Fibonacci-like sequences and see if they help us out. This is something mathematicians do frequently; sometimes when we can't solve something, we look in a more general context and see if it gives us insight. Or at minimum, we at least have a new object which we also don't understand, which is fun too. 

So, what happens if we ask if every Fibonacci-like sequence contains infinitely many prime values? Well, here the answer is obviously false. Consider the example we gave above where we had earlier 2, 2, 4, 6, 10, 16... Every term is even, so obviously it doesn't contain any primes after 2. And we can do similar tricks: For example, look at the Fibonacci-like sequence 3, 9, 12, 21, 33, 54, 87... This sequence has every element divisible by 3? Why? Because both the first two terms were divisible by 3, and the sum of two multiples of 3 has to also be a multiple of 3. So at each stage, we get a new multiple of 3. 

Given this we can construct a lot of Fibonacci-like sequences which not only don't have infinitely many prime values, they don't have any prime values. For example, we could start with 10, 25 as our starting values, and we'd get a sequence where every term is divisible by 5.

Ok. So our original question had an answer of no. But for boring reasons. Let's call a Fibonacci-like sequence interesting if the first two terms don't have any common factor greater than 1. So the Fibonacci numbers themselves match this, as does our sequence 1, 3, 4, 7, 11... Let's look at a few others: Let's start with 9 and 25. So we get 9,25, 34,59 . Hmm, we eventually got a prime at least. Let's do another, how about  8 and 17. We get 8, 17, 25, 42, 67. Again we got a prime. 

Now here's the interesting question: Does every interesting Fibonacci-like sequence eventually have at least one prime value? Perhaps surprisingly, the answer to this is also no. Ron Graham (Who recently passed awy) back in 1964, found that the answer is no. But the starting values Graham found were very big. Since then there's been some effort to find the smallest pair of starting values which don't give rise to any primes. But the smallest known pair today is still very big. It is known   that if one starts with 106276436867 and  35256392432 then the resulting Fibonacci-like sequence has no prime values. The basic idea of finding numbers like this is to find a finite set of primes such that any member of one's sequence is divisible by at least one of the primes. But constructing these is hard. 

But the existence of Graham-like sequences shows that if there are infinitely many Fibonacci primes, then the proof has to use something deep, beyond just the very basics of the sequence itself. There is however a generalization of the claim that there are infinitely many Fibonacci primes which seems plausible, and I have not seen stated explicitly in the literature.  It seems plausible that if a given interesting Fibonacci-like sequence contains at least one prime, then it must contain infinitely many. This is, if true, probably a very difficult thing to prove, since it would be stronger than the apparently tough open problem about Fibonacci primes themselves. If the above is false, it may be that the same techniques as used in Graham's result can find a counterexample. However, it seems  likely that there is some number k such that if an interesting Fibonacci-like sequence contains at least k primes then it contains infinitely many.

I've mentioned before that there are a lot of simple to state open math problems that are not so famous. Let's talk about another of them: The perfect cuboid problem, sometimes called the Euler brick problem.

The Euler brick problem/perfect cuboid problem is to find an example of a rectangular box such that every side length, each face diagonal, and the internal diagonals are integers. We call such an object a perfect cuboid.

We have examples of where all sides and face diagonals are integers. An example is a box with width 44, length 117, and height 240. But there no known example where every face and the internal diagonals are integers.

In 2009, Jorge Sawyer and Clifford Reiter discovered examples of parallelepipeds (that is a box with parallelograms for sides) where are all sides, face diagonals and internal diagonals, are integers.

There are a lot of restrictions on what a perfect cuboid must look like. For example, we know that the smallest side must be at least 10^10. This number has been claimed to be pushed up the last few years but those higher searches have not yet been peer reviewed as far as I'm aware. One natural thing one can try to prove that the sides must be divisible by various primes. For example, one can without too much work show that at least one of the edge's must be divisible by 5. More generally, if one lets p be any prime of the set 2, 3, 5, 7, 11, 13, 17, 19, 29, 37 then at least one edge, face diagonal or internal diagonal must be divisible by p. You may note that the list above skips 23 and 31; the obvious sort of arguments don't seem to work for those two. Extending this to larger primes likewise seems difficult.

The Abel Prize was just rewarded to Hillel Furstenberg and Gregory Margulis for their use of methods from probability and dynamics in group theory, number theory and combinatorics. I've interacted with both of them. I took complex analysis with Margulis when I was an undergrad. My interaction with Furstenberg was more limited, talking to him a few times when he was visiting, mainly when I was an undergrad. Hillel seemed willing to listen to whatever half-baked idea an undergrad had that was connected to something he did.

People often think of the Fields Medal as the equivalent of a Nobel in math, but the Abel prize has a pretty similar stature.

To give some idea of what they did, let's talk about random walks. Imagine you are on a standard number line, starting at zero. You take turns flipping a coin. If you get a heads, you walk one unit in the positive direction and if you get tails, you walk one unit in the negative direction. As you repeat this, you wander somewhat randomly; this is thus called a random walk.

There are a lot of questions you can ask. For example, how likely is it that I'm going to end back where I started? It turns out that if you play this game, you'll find your way back home infinitely many times with probability 1. We can also ask, in general if I play this game t steps, about how far should I expect to be from where I started? I could keep almost always hitting heads, but that seems unlikely. It turns out that your distance from the origin is almost surely not higher than roughly the square root of the number of steps you have taken. (It also turns out that this fact is closely related to one reason we believe the Riemann Hypothesis is true, but that's a story for another time.)

One interesting thing we can do is try to ask the same questions in higher dimensions. Imagine a random walk in two dimensions. Now, instead of flipping a coin, we roll a four sided die, and depending on the result go one unit left, one unit right, one unit up, or one unit down. It turns out that the answers here to our questions above remain the same. We'll still be no more than about square root of our number of steps from the origin, and we'll still return to the origin infinitely many times almost surely.

What about three dimensions? Now we have six possible directions. And now things change! The square root claim is still true, but we don't expect to return to the origin infinitely many times. In this sense, a wandering ant will eventually find its colony, but a wandering bird might not find its nest.

Part of what Margulis and Furstenburg did was they realized that by asking questions about things like the above on abstract objects rather than the space one is used to, they could better understand the structure of those objects.

One idea that they worked with is applying notions from ergodic theory in a similar context. Ergodic theory is a branch of what is sometimes called "chaos theory" and studies systems which unlike the random walks have no intrinsic randomness, but are still hard to predict. Consider for example, the following function: We'll start with a number between 0 and 1 (inclusive), and we'll double it. If the resulting number is greater than 1, we'll then subtract 1, and if not we'll keep that number. Let's look at three example numbers.

Let's start with 1/3. The first time, we double it, so we get 2/3. Then we double again so we get 4/3. That's greater than 1, so we subtract 1 to get 1/3. And we're back where we started. So this formed a loop. But not all numbers form a loop this way, and in fact most numbers don't.

Imagine we started with 25/48. We have then 2(25/48) = 25/24, so we have to subtract 1 to 1/24. We then get 1/12, then 1/6, then 1/3, and we're now in the loop from 1/3. But that loop didn't contain 25/48 to start with. So a number might end up in a loop where the loop doesn't itself contain the number.

But some numbers never end up in a loop at all. Let's look at an example.

Let's start with sqrt(2)-1 which is about .414... Now, we double we get 2(sqrt(2)-1) = 0.828... We'll double and subtract 1 to get 4(sqrt(2)-1)-1 = 0.656... and we'll do this again to get 2(4(sqrt(2)-1)-1) -1 = 0.313... If we double again, we won't need to subtract 1, so we'll have 2(2(4(sqrt(2)-1)-1) -1) = 0.616... and so on. It turns out we never get in a loop. Worse, numbers very close to each other might behave very differently. sqrt(2)-1 and sqrt(2) -1 +1/108 are very close together as numbers, but if you do this process more than a few times, to each, you'll find that your process for each starts looking completely unrelated in terms of how large one is at a given stage compared to the other. Margulis and Furstenburg applied ideas about how to understand systems like this to other areas of math. That's now a very big area of study, and a lot of it is owed to their work on it.

Note: I'm in the process of copying some older math posts from Facebook over here. with some modification This is one of those.

I mentioned Lehmer's Conjecture in an earlier post. Recently, someone asked me how one goes about proving something like the sort of result that a couunterexample needs to have a lot of distinct prime factors. I wrote an answer to them, and this is a version of that answer which may be of interest to people who read the earlier post. This post is slightly more technical than most of the other math posts currently here.

The primary technique used is the following. In what follows, I'll write capital N for a counterexample to Lehmer's conjecture, and use n for a generic integer where we aren't necessarily making that assumption. I'll implicitly assume that you've seen the Euler phi function a bit before. If not, the Wikipedia article is a good place to start . But the main takeaway we need about it is that if I have n=p^a for some prime p, then I can write phi(n) = (p-1)p^(a-1), I can multiply together the phi values at each highest prime power which divide n. For example, if n = 360, 180 =2^3 * 3^2 * 5 I can write phi(360)= phi(2^3) phi(3^2) phi(5) = (2-1)2^2 * (3-1)3^1 * (5-1) = 4*2*3*4=96. This formula will come in handy below. We won't need any other properties beyond what was mentioned in the previous post about Lehmer's Conjecture.

In the below, we'll write a|b to mean that a is a divisor of b. For example, 3|6 is true but 4|6 is false. We'll need two preliminary remarks:

First, note that any such N must be odd. To see this, note that since phi(n) is even for n>2, if N is a counterexample, then N must be odd, since if N were even, N-1 would not be divisible by phi(N).

Second, note that any such N must be squarefree (that is not divisible by the square of a prime). To see this, note that from the standard formula for phi(n), if p^2 |n, then p|phi(n).

So if N is divisible by p^2 for some prime p, then since p|phi(n), we'll have p|N-1 and p|N which is impossible.

We'll define H(n) as the product of p/(p-1) over all primes which divide n. For example, H(60)= (2/1)(3/2)(5/4) = 15/4.

Important things to note about H(n). First, H(n) is multiplicative; that H(ab)= H(a)H(b) whenever a and b have greatest common divisor 1. Second, since x/(x-1) is a decreasing function, so if we replace a prime in the factorization of n with a larger prime, the value of H goes down. For example, H(3) > H(5) and H(20) > H(45).

Notice that H(n) = n/phi(n). Now, if phi(N)|N-1 for some composite N, then k phi(N) = n-1 for some k >1, and therefore we have H(n) = n/phi(n) > (n-1)/phi(n) = k. In particular, for any such N one must have H(N) > 2.

From this one immediately has that any such N has to have at least three distinct prime factors. To see this, note that H(15) = (3/2)(5/4) = 15/8 < 2, and again replacing any prime with a larger prime would result in H being even smaller.

To give a flavor of the general method, let's sketch a proof that N needs to have at least five distinct prime factors.

One Lemma that will be helpful first:

Lemma 1: If N is a counterexample to Lehmer's conjecture and p|N for some prime p, and q|N for some prime q then we cannot have p|q-1.

(For example, this Lemma shows that we cannot have both 3|N and 7|N. Very handy little bit.)

Theorem: There is no such N with three distinct prime factors.

Proof: Assume that N is such an N. Note that (5/4)(7/6)(11/10) < 2. So our smallest prime factor must be 3. So 7 does not divide N by our Lemma. Similarly, since (3/2)(11/10)(13/12)< 2, our second largest prime factor must be 5, and thus by our Lemma our third prime factor cannot be 11. It also cannot be 13 by our Lemma. We now need a prime p (3/2)(5/4)(p/(p-1) > 2. But solving this inequality one will find that one needs p<17, so there are no primes which remain to check.

Now we'll sketch the same technique for the slightly harder case of four distinct prime factors. But the above shows most of the central ideas. Below will be essentially just an elaboration of the same technique.

Theorem: No such N has four distinct prime factors.

Proof:We'll break this down into two cases, based on whether 3 is a prime factor of N.

Case I:Assume 3|N. By our Lemma, we cannot have 7, 13 or 19 as divisors of N. Now, we'll break this down into two subcases based on whether 5|N.

Case Ia: 5|N. In that case, by our Lemma we have that 11 does not divide N. Let's break this down slightly further. Note that if the second largest prime factor of N is 29 then since (3/2)(5/4)(29/28)(47/46)< 2 we have a contradiction. (Exercise: Why was I able to get away with skipping 31, 37, 40 and 43 as possible prime divisors?). So we have some subcases where the third prime factor is 17, 23 or 29. If the third prime factor is 17, then we must have for the fourth prime factor p, that (3/2)(5/4)(17/16)(p/(p-1)) > 2. Solving for this, one will find that one must have p <= 257. Now, checking all primes which are at most 257 will find that none of them work. Similarly, one can do the same thing if the third prime is 23 or 29. (If one is lazy and is doing this with a computer one doesn't even need to calculate the precise largest bound for when (3/2)(5/4)(23/22)(p/(p-1)) > 2, since we know it must be no higher than 257. The same remark applies to 29.)

Case Ib, where 5 is not a divisor of N. Then we have (3/2)(11/10)(17/16)(23/22) < 2 so we're done. (Note that if this hadn't been less than 2 we could have used that we can't actually have both 11|N and 23|N so we could have broken this down further but we didn't need to).

Case II: We've assumed that 3 doesn't divide N. Note that (5/4)(7/6)(11/10)(13/12) < 2, so we're done. (Again note that if this had been too large we could have broken down into subcases depending on whether 5 divides N and then thrown 11 out in one of them.)

That's the basic technique. In practice, one wants to do as much of this as one can via computers and there are a few other ideas and tweaks which one can do to save on case checking.

(Note: I'm in the process of copying some older math posts from Facebook over here. This is one of those posts.)

I've mentioned before that there are a lot of simple to state but not so incredibly famous open problems. I want to talk about two thematically related problems, Lehmer's Totient Problem, and Carmichael's Conjecture. These problems are well known to number theorists but don't have the same general fame as say Goldbach's Conjecture or the existence of odd perfect numbers.

Recall two numbers are relatively prime when their greatest common divisor is 1. For example, 15 and 8 are relatively prime. But 21 and 15 are not relatively prime because their GCD is 3. We'll define phi(n) to be the number of positive integers which are less than or equal to n and relatively prime to n. This function is known as the Euler phi function. For example, phi(9) =6 because under 9 we have 1,2,4,5,7 and 8 as numbers which are relatively prime to 9. Note that if p is a prime, then phi(p)=p-1. For example, phi(5) =4 since the numbers which are less than or equal to 5 and relatively prime to 5 are everybody: 1,2,3 and 4. (If you haven't seen the phi function before, it might be worth playing around with. Can you find phi(20)? What is phi of a power of 2? What is phi of a prime power in general?)

For a given positive integer a and another integer n we want to understand how big the smallest positive integer k is so that a^k leaves a remainder of 1 when we divide by n. For example, if a =2 and n =5, then one may take k=4, since 2^4 = 16 which leaves a remainder of 1 when we divide by 5. Similarly, if a=4 and n=7, then k = 3, since 4^3 = 64 which leaves a remainder of 1 when divided by 7.

Such a k doesn't always exist for a given n. If a and n share a common factor greater than 1, then so will a^k and n, and so the remainder of a^k when divided by n will also share the common factor, and so the remainder cannot be 1. For example, let's look at powers of 2 and their remainder when we divide by 10. We have 2,4, 8, 16, 32,64, 128, 256. When we divide by 10, we get as remainders 2,4,8, 6, 2,4,8, 6 ... And it keeps repeating this way.

But maybe there always is such a k as long as a and n are relatively prime. This turns out to be the case.

The first step towards proving this was due to Fermat. He proved what is now often called "Fermat's Little Theorem" (to contrast it with "Fermat's Last Theorem" but confusingly also abbreviated as FLT) which was that if p is prime, and a is not divisible by p (hence they must be relatively prime) then a^(p-1) leaves a remainder of 1 when one divides by p. So when n=p, we can in this situation always take p-1. The number p-1 may remind you of something, which we had earlier. When p was prime we had phi(p)=p-1. (A good exercise is to verify this works with p=7. That is, check that a^6 always leaves a remainder o 1 when you divide by 7 for a=1,2,3,4,5 or 6.)

And this is in fact the proper generalization! Euler proved a much stronger result: Recall we defined phi(n) be the number of positive integers which are less than or equal to n, and which share no common factor greater than 1 with n. Then Euler proved that if a and n share no common factor, then aphi(n) leaves a remainder of 1 when I divide by n. So, for k we care about is always at most phi(n). One might be interested in given an a and n what is the least value of k, and that's a delicate question that my own PhD work touched on. But that's a separate question. Phi(n) also shows up in some practical cryptographic applications, but that's not our emphasis today.

D. H. Lehmer in the 1930s was interested in how if p is a prime, then phi(p)=p-1. Lehmer noted that if n is composite then obviously phi(n) has to be strictly smaller than n-1, but maybe it fits in neatly to n-1. That is, maybe there is a composite number where phi(n) divides n-1? Lehmer conjectured that this was not the case. We don't know, but we do know that if there is such a number it needs to be pretty big (greater than 10^22 ), and it needs to have at least 15 distinct prime factors. If someone has the time and effort with some decent amount of computing power, they could likely improve this substantially. The technique used to obtain that bound is a little more clever than just checking every number under 10^22, but it doesn't involve deeply subtle number theory. My suspicion is that someone who is a good algorithmist and with some access to decent computing power should be able to improve that bound.

The other conjecture worth talking about in this context is Carmichael's Conjecture. Carmichael noticed that some numbers never arise as the value of phi(n). For example, phi(n) is always even if n >2. To see this note that if b is relatively prime to n, then so n-b, so after 2, numbers relatively prime to n and less than n always come in pairs. So any odd number other than 1 is never the value of the phi function. With a bit more work one can show that some other numbers don't arise either. For example, phi(x)=14 has no solutions.

But, Carmichael noticed that when there was a solution to phi(x)=k, there always seemed to be another y such that x was not equal to y and phi(y)=k. For example, we saw earlier that phi(5)=4. But phi(8) =4 also, since 1, 3,5 and 7 are the numbers which are less than or equal to 8 and relatively prime to 8. Carmichael conjectured that this was always true. That is, if phi(x)=k had a solution, then there was always more than one solution. Another similar example is how we saw that phi(9)=6, but it is also the case that phi(7)=6. (A good exercise: There are two other m such that phi(m)=6. Can you find them?). In this case, we also have very large bounds. In particular, we know that any counterexample to Carmichael's conjecture must be greater than 10^(10^10). That's pretty big.

(Note: I'm in the process of copying some older math posts from Facebook over here with some slight modifications. This is one of those.)

There are a lot of times people talk about famous open mathematical problems. But less attention is paid to some of the problems that are both simple to state and aren't very famous at all. Let's talk about one of those not so famous but still simple open problems.

We're interested in the minimum number of 1s needed to write a positive integer n as a product or sum of 1s, using any number of parentheses, and we'll call that ||n||. For example, the equation 6=(1+1)(1+1+1) shows that ||6|| is at most 5, since it took 5 1s. A little playing around will convince you that you cannot write 6 using just four or fewer 1s, so it is really is the case that ||6||=5. We call ||n|| the integer complexity of n.

Now here's the problem: Does every power of 2 have a most efficient representation the obvious way? That is, is it is always true f(2^k)= 2k? For example, 8=(1+1)(1+1)(1+1) and in fact ||8||=6. Similarly, 16 = (1+1)(1+1)(1+1)(1+1), and ||16||=8. (Note that we sometimes have representations which are tied for writing it this way; for example we can also write 8 = (1+1+1+1)(1+1) but that also takes 6 ones, not fewer).

One might think that the answer should be obviously yes, so let's look for a moment at powers of 5. Does every power of 5 have the obvious representation as best? We'd expect from ||5||=5, to get that ||25||=10, and we do. The pattern continues with ||5^3||=15, and ||5^4||=20, and ||5^5||=25, but then it breaks down, ||5^6||=29. This in some sense happens because 5^6-1 has a lot of small prime factors. But it isn't obvious that something similar couldn't happen with powers of 2. This problem was as far as I'm aware, first proposed by Richard Guy. This is a problem which is dear to me and one which I'm responsible for some of the progress on with Harry Altman who has written a lot about this problem on his Dreamwidth discussing his published works on the problem.

My intuition on this problem keeps jumping back and forth on whether it is true or not. Right now, I'm leaning towards it being false.

(Note: I'm in the process of copying some older math posts from Facebook over here. This is the first of those.)

In school, one often learns to solve equations in a single variable, something like x^2-5x+6=0. But when one has more than one variable what can one say about the solution set? For example, one might have x^2 -2y^2 =1 which has a lot of solutions.

One thing we're interested in is equations with possibly more than one variable, but we only care about integer solutions. For example, in our equation x^2- 2y^2 =1, we might care about solutions like x=1, y=0, or x=-1 and y=0, or the solution x=3 and y=2, but we won't care about solutions like x=2 and y = 1.225 ... When we care about an equation's integer solutions only we'll call it a Diophatine equation. This is a term named after the Greek mathematician who studied similar equations; most of the time Diophantus himself was interested in the slightly broader set of rational solutions, but the name stuck. It turns out that x^2 -2y^2 =1 has infinitely many integer solutions, but establishing that takes more work.

Sometimes a Diophantine equation has no solutions at all. For example, let's look at x^2 + y^2 = 3. How can we tell that this equation has no integer solutions? Well, one way of doing so is to notice that if x=a and y=b is a solution, then so is x=-a, and y=-b, because x and y are always squared in this equation, and (-m)^2 = m^2 for any m. But, if x is at least 2, then x^2 is at least 4, and 4+0 is already greater than 3, so we need only look at options where x and y are either 0 or 1. Now, we can just check the possibilities 1^2+0=1 which is not 3, and 0^2+0^2 = 0 which is not 3, and 1^2+1^2 = 2 which is not 3.

What about a slightly harder equation? What if we want to look at the Diophantine equation x^2 + y^2 = 3+4t. It seems like this equation should be much harder than the previous one. Any proof that this equation doesn't have any solutions should trickier than the proof that x^2+y^2 = 3, because that equation is a special case of this one; in particular that equation is when we insist that t=0 in our new equation.

It seems that our previous method won't work because if t is big, then x or y could be large also. So for x^2+y^2=3+4t we can't in any obvious way reduce the set of solutions to just a finite set to check. Or can we?

Instead of looking at a finite set of integers, we'll look at the remainders of x and y when we divide by 4. We'll write the remainder of a when divided by b as "a (mod b)", and we'll say that two numbers are equivalent mod b if they have the same remainder when we divide by b. For example, 10, 4 and 16 are all equivalent mod 6, because they all leave a remainder of 4 when we divide by 6. Similarly, 5 and 9 are not equivalent mod 3, because 5 leaves a remainder of 2 when we divide by 3, but 9 leaves a remainder of 0. Let's look at the remainders of n^2 when we divide by 4.

1^2 = 1 = 1 (mod 4) . 2^2 = 4= 0 (mod 4), 3^2 = 9 = 1 (mod 4), 4^2 = 16 = 0 (mod 4). We might notice a pattern here, that any perfect square leaves a remainder of either 1 or 0 when we divide by 4.

Let's see why that's the case. If n is an even number then we can write n=2k for some integer k. Then n^2 = (2k)^2 = 4k^2 = 4(k^2) so n^2 leaves a remainder of 0 when we divide by 4. If n is odd, then n=2k+1 for some k, and in that case n^2 = (2k+1)^2 = 4k^2+4k+1 = 4(k^2 +k)+1 so, n^2 in that case leaves a remainder of 1 when we divide by 4.

Great, how is this relevant to trying to understand whether x^2 + y^2 = 3+4t has any integer solutions? Here's the key: we know that x^2 has a remainder of 1 or 0 when we divide by 4, and the same goes for y^2, so their sum x^2 + y^2 can have a remainder of 1+0, 0+1, 1+1 or 0+0 when we divide by 4. That means that no matter what values we choose for x and y, x^2 + y^2 will have a remainder of 0, 1 or 2 when we divide by 4; it will never have a remainder of 3. But 3+4t will always have a remainder of 3 when we divide by 4. So, there's no way that two sides can ever be equal, because their remainders will always be different.

One can often use this sort of approach. For example, one can look at remainders when dividing by 3, to show that x^2 = 2 + 3y doesn't have any integer solutions. (This is a good exercise.)

Sometimes an equation has no solutions other than a "trivial" solution. For example, we could take our earlier equation x^2 + y^2 = 3+4t and modify it to get (x^2 + y^2)(x^2 + y^2 + t^2) = (3+4t)(x^2 + y^2 + t^2). This new equation has a silly solution, x = y=t=0. But it doesn't have any other solutions; to see this note that if x^2 + y^2 + t^2 is not zero, then we can divide by it so we get just our original equation x^2 + y^2 = 3+4t back. But if x^2+y^2+t^2 =0, then we must have x=y=t=0.

Many equations have a solution where all the variables are zero, but no other solutions. For example, x^2 = 2y^2 only has the solution x=0 and y=0 (See if you can see why.)

One might hope that maybe when a Diophantine equation doesn't have solutions other than a trivial solution, one can always use these methods, either just looking at remainders, or being able to bound how big the variables can be and solving accordingly, or at least other similarly simple methods. But alas, this is not the case. There are equations where there are no solutions, but where no remainder argument will ever show you that.

A somewhat "famous" example is the Cassels-Guy cubic 5x^3 + 9y^3 + 10z^3 + 12w^3 = 0

This Diophantine equation has no solutions other than all variables being equal zero, but if you pick any n and try to look at the remainders when one divides by n, you'll never get a contradiction just from that, and in a certain deeper sense, even techniques which generalize the remainder argument won't ever tell you that there are no solutions. And if one lists other similarly simple methods, one can show that they won't lead to a contradiction either.

The Cassels-Guy cubic is annoying for another related reason. One might naively guess that if an equation has lots of variables that it should have non-zero solutions as long as there aren't any such remainder issues, since more variables give more room/flexbility. One can try to make this notion mathematically precise, but the obvious precise versions of this would incorrectly predict that the Cassels-Guy cubic does have nonzero solutions.

In 1900, the David Hilbert listed 23 problems that he thought should be of the most importance for mathematicians to try to resolve in the 20th century. One of those problems, the 10th problem, was to find an algorithm which given a Diophantine equation tells you whether or not it has solutions. In the 1950s, Martin Davis and Julia Robinson almost showed that there was no such algorithm. They proved that there was no such general procedure if one allowed a slightly larger set of equations than what is normally called a Diophantine equation. In particular, note that in all of our examples, we've never had a variable in an exponent. For example, we haven't looked at something like 2^y = x^t + x^2 + x. Robinson and Davis proved that if one is allowed to have such equations (sometimes called "exponential Diophantine equations") that there was no algorithm to tell whether such an equation had solutions.

A few years later, Yuri Matiyasevich, building on their work showed that even for regular Diophantine equations, there was no solution to Hilbert's tenth problem. An important role was shown by essentially showing that one can make a Diophantine equation whose solution set in a certain sense looks exactly like the Fibonacci numbers. One consequence of Matiyasevic's work was that even if one insisted that no variable be raised to a power higher than the fourth power, there was still no such algorithm. One obvious question then arises is whether the same thing is true for equations where there's no variable raised to a power greater than 3. No one knows. The Cassels-Guy cubic shows that if an algorithm does exist to solve such equations, it must have some substantial subtlety behind it.