Mathematicians Find a New Class of Digitally Delicate Primes

Take a look at the numbers 294,001, 505,447 and 584,141. Notice anything special about them? You may recognize that they’re all prime — evenly divisible only by themselves and 1 — but these particular primes are even more unusual.

If you pick any single digit in any of those numbers and change it, the new number is composite, and hence no longer prime. Change the 1 in 294,001 to a 7, for instance, and the resulting number is divisible by 7; change it to a 9, and it’s divisible by 3.

Such numbers are called “digitally delicate primes,” and they’re a relatively recent mathematical invention. In 1978, the mathematician and prolific problem poser Murray Klamkin wondered if any numbers like this existed. His question got a quick response from one of the most prolific problem solvers of all time, Paul Erdős. He proved not only that they do exist, but also that there are an infinite number of them — a result that holds not just for base 10, but for any number system. Other mathematicians have since extended Erdős’ result, including the Fields Medal winner Terence Tao, who proved in a 2011 paper that a “positive proportion” of primes are digitally delicate (again, for all bases). That means the average distance between consecutive digitally delicate primes remains fairly steady as prime numbers themselves get really big — in other words, digitally delicate primes won’t become increasingly scarce among the primes.

Now, with two recent papers, Michael Filaseta of the University of South Carolina has carried the idea further, coming up with an even more rarefied class of digitally delicate prime numbers.

“It’s a remarkable result,” said Paul Pollack of the University of Georgia.

Motivated by Erdős’ and Tao’s work, Filaseta wondered what would happen if you included an infinite string of leading zeros as part of the prime number. The numbers 53 and …0000000053 have the same value, after all; would changing any one of those infinite zeros tacked on to a digitally delicate prime automatically make it composite?

Filaseta decided to call such numbers, assuming they existed, “widely digitally delicate,” and he investigated their properties in a November 2020 paper with his former graduate student Jeremiah Southwick.

Not surprisingly, the added condition makes such numbers harder to find. “294,001 is digitally delicate, but not widely digitally delicate,”  Pollack said, “since if we change …000,294,001 to …010,294,001, we get 10,294,001” — another prime number.

In fact, Filaseta and Southwick couldn’t find one example in base 10 of a widely digitally delicate prime, despite looking through all the integers up to 1,000,000,000. But that didn’t prevent them from proving some strong statements about these hypothetical numbers.

First, they showed that such numbers are indeed possible in base 10, and, what’s more, an infinite number of them exist. Going a step further, they also proved that a positive proportion of prime numbers are widely digitally delicate, just as Tao had done for digitally delicate primes. (In his doctoral dissertation, Southwick achieved the same results in bases 2 through 9, 11 and 31.)

Pollack was impressed with the findings. “There are infinitely many possible things you’re allowed to do to these numbers and, no matter which you do, you’re still guaranteed a composite answer,” he said.

The proof relied on two tools. The first, called covering systems or covering congruences, was invented by Erdős in 1950 to solve a different problem in number theory. “What a covering system does for you,” Southwick said, “is to give you a large number of buckets, along with a guarantee that every positive integer is in at least one of those buckets.” If, for example, you divide all positive integers by 2, you’ll end up with two buckets: one containing even numbers in which the remainder is 0 and one containing odd numbers in which the remainder is 1. In this way, all positive integers have been “covered,” and the numbers occupying the same bucket are considered “congruent” to each other.

The situation involving widely digitally delicate primes is more complicated, of course. You’ll need a lot more buckets, something on the order of 10^25,000, and in one of those buckets every prime number is guaranteed to become composite if any of its digits, including its leading zeros, is increased.

But to be widely digitally delicate, a prime number must also become composite if any of its digits is decreased. That’s where the second tool, called a sieve, comes in. Sieve methods, which date back to the ancient Greeks, offer a way of counting, estimating or setting limits on the number of integers that satisfy certain properties. Filaseta and Southwick used a sieve argument, similar to the approach Tao took in 2011, to show that if you take prime numbers in the aforementioned bucket and decrease one of the digits, a positive proportion of those primes will become composite. In other words, a positive proportion of those primes are widely digitally delicate.

“The Filaseta-Southwick theorem,” Pollack said, “is a beautiful and unexpected illustration of the power of covering congruences.”

Then, in a January paper, Filaseta and his current graduate student Jacob Juillerat made an even more astonishing claim: There exist arbitrarily long sequences of consecutive primes, each of which is widely digitally delicate. It would be possible, for instance, to find 10 consecutive primes that are widely digitally delicate. But to do so, you’d have to examine a huge number of primes, Filaseta said, “probably more than the number of atoms in the observable universe.” He compared it to winning the lottery 10 times in a row: The odds of doing so are extraordinarily slim, but still nonzero.

Filaseta and Juillerat proved their theorem in two stages. First, they used covering system arguments to prove that there is a bucket containing infinitely many primes, all of which are widely digitally delicate. In the second step, they applied a theorem, proved in 2000 by Daniel Shiu, to show that somewhere in the list of all primes, there exists any arbitrary number of consecutive primes contained in this bucket. Those consecutive primes, by virtue of being in that bucket, are necessarily widely digitally delicate.

Carl Pomerance of Dartmouth College thoroughly enjoyed these papers, calling Filaseta “a master at applying covering congruences to many interesting number theory problems. Mathematics can be an exercise in bringing powerful tools to bear, and it can also be pure fun.”

At the same time, Pomerance noted, representing a number in terms of its digits in base 10 might be convenient, “but it doesn’t go to the essence of what that number really is.” There are more fundamental ways of representing numbers, he maintained, such as the way Mersenne primes are defined — prime numbers of the form 2^p – 1 for a prime p.

Filaseta agrees. Nevertheless, the recent papers raise questions that may be worth exploring. Filaseta is curious as to whether widely digitally delicate primes exist in every base. Juillerat, for his part, wonders whether “there are infinitely many primes that become composite when you insert a digit between two digits, instead of just replacing a digit.”

Another tantalizing question comes from Pomerance: Do all primes eventually become digitally delicate or widely digitally delicate as you approach infinity? Equivalently, is there a limited number of primes that are not digitally delicate (or widely digitally delicate)? He feels that the answer to that question, however it is phrased, must be no. But he and Filaseta consider it an intriguing conjecture, one that neither of them knows how to prove without relying on another unproved conjecture.

“The story of mathematical research is that you don’t know beforehand if you can solve a challenging problem or whether it will lead to something important,” Pomerance said. “You can’t decide in advance: Today I’m going to do something valuable. Though it’s great, of course, when things turn out that way.”