Sunday, July 3, 2022

Perfect numbers: Lichtman's Theorem (Part 1)

This summer, we are working through Jared Lichtman's recent proof that the primes achieve the maximal Erdős sum over primitive subsets of the natural numbers.

Quanta Magazine had a very nice article describing the theorem (formerly a conjecture of Erdős) which is the inspiration for this project. The article is here.

I will be posting notes on our conversations. The most important thing to understand: this project is about the journey and not the destination. We may not (probably won't!) get all the way through the paper. Along the way, we will take plenty of detours and excursions.

Examples of Primitive Sets

We started with the definition of primitive sets and tried to come up with examples.  I loved Jin's first example: $\{2\}.$ The first three examples in the paper were easy:

  • Dyadic interval $(x,2x].$  As an aside, who uses $x$ as their preferred variable for a natural number like this!
  • Primes: Jin and Jate thought of this immediately after getting the definition of primitive set.  
  • All natural numbers with exactly $k$ prime factors for a fixed $k\ge 1.$ The paper emphasized counting factors with multiplicity, but, of course, that isn't necessary to get a primitive set. This linked to two ideas: (a) the subset of a primitive set is also primitive and (b) a sense of expanding a primitive set until we have a maximal version that doesn't allow any additional members.

We had to pause for perfect numbers. In the paper, Lichtman gives a footnote for the definition of perfect numbers. We had expected a citation/short explanation of why perfect numbers are a primitive set.  Feels odd that someone could read this paper and not know the definition of perfect numbers (but would immediately see how they were a primitive set.)

Sigma function

To investigate whether a perfect number could be a multiple of another perfect number, we started exploring

$$\sigma(n) = \sum_{d\mid n} d$$

and $\sigma(n)/n.$

We first built some numerical experience, working through $\sigma(p),$ $\sigma(p^2),$ $\sigma(2^m),$ $\sigma(p^m),$ and $\sigma(pq)$ for distinct primes $p$ and $q.$

We made a conjectures that, for $m$ and $n$ relatively prime, $\sigma(mn) = \sigma(m)\sigma(n),$ but haven't proven this yet.

Coming back to perfect numbers, we noticed that $\sigma(m)=2m$ when $m$ is perfect. 

We then started looking at $\sigma(n)/n.$ Again, we began with data, building a table with $n$ from 2 to 9 and started making conjectures. The first conjecture was that this function falls as we move from even to odd $n$ and then rises when we go back to even.  In other words:

$$\frac{\sigma(2n+1)}{2n+1} < \frac{\sigma(2n)}{2n}$$

and $$\frac{\sigma(2n+1)}{2n+1} < \frac{\sigma(2n+2)}{2n+2}$$

This led us to add more data, testing 15, 16, 25, 26, 27. Eventually, Jate came up with 105, where we noticed that the second part of the conjecture fails:

$$\frac{\sigma(105)}{105} = \frac{(1+3)\cdot(1+5)\cdot(1+7)}{105}=\frac{192}{105}$$

$$\frac{\sigma(106)}{106} = \frac{(1+2)\cdot(1+53)}{2\cdot 53}=\frac{162}{106}$$

In typing up these notes, I realize that we haven't falsified the first part of the conjecture. In fact, we didn't even check $\sigma(104)/104$ and $\sigma(107)/107$ (both of which are actually consistent with the first part of the conjecture.  We will return to this open thread.

Finally, we noticed that we could rewrite $\sigma(n)/n$ as:

$$\frac{\sigma(n)}{n} = \sum_{d\mid n}\frac{1}{d}.$$

This allowed us to realize that, if $m\mid n$ then $\sigma(m)/m < \sigma(n)/n$ because the relevant sum for $n$ will contain all of the terms in the sum for $m$ and additional ones. From there, it was trivial to see that a perfect number could not be a multiple of another perfect number.

We talked briefly about how many perfect numbers there are. Jate had heard that all even perfect numbers are of the form $2^{p-1} (2^p-1)$ where $2^p-1$ is a prime (called a Mersenne prime.) This led us to ask whether we could nicely add anything to the perfect numbers and still keep the set primitive. Following an idea in this Carl Pomerance talk, we defined the minimal nondeficient numbers (we didn't use this name, though!):

$$\{ n: \sigma(n)/n \ge 2 \textrm{ and } \forall m<n \textrm{ with }m\mid n, \sigma(m)/m < 2\}$$

We talked about how this would be a primitive set and then tried to find some elements that were not perfect.  We stopped for dinner before we found an example, so this is another open thread.

A picture of our written notes on the exploration are below.

What is big

The example of dyadic intervals shows that we can make a finite primitive set of any size that we want. Are these large primitive sets?  Clearly, if there are infinite primitive sets (like the primes) then any finite primitive set is not very big. However, Jate was still intrigued about the question of whether the collection of dyadic intervals has some form of interesting maximal element that could be considered on-par with the infinite primitive sets.

We talked about at least one limit concept: for a family of sets within a given set $A_n\subset X$ for $n\ge 1,$ we can think of a limit set defined as the eventual members by:
$$A = \{x\in X : \exists N \textrm{ such that } \forall n\ge N, x\in A_n\}$$

In this case, the limit set associated with the dyadic intervals is actually empty. Jate was still interested in finding a way to salvage the sense that the dyadic intervals are getting bigger without limit. This is an open thread.

The other notion we discussed was the asymptotic density.  Some additional open threads to consider for the future:
  • calculating other asymptotic densities
  • prime number theorem
  • the Erdős sum (of course we will follow this one!) 

No comments:

Post a Comment