November 17, 2012

The Deimel Conjecture

I heard an interview with mathematician Thomas Hales on the radio yesterday. Hales is notable for having apparently proved the Kepler conjecture. The interview made me realize that I have devised at least two propositions that might be called the Deimel conjecture.

A conjecture, in this sense, is essentially a proposition one suspects is true (i.e., is a theorem) but which one has been unable to prove. A meaningful conjecture, as long as it remains a conjecture, is either very difficult to prove, false, or unprovable.

The first significant conjecture I posited involves my dissertation work in automata theory. It is not clearly interesting (i.e., important) and, in any case, is difficult to state concisely. What I will offer as the Deimel conjecture is not clearly interesting either, but it is reasonably easy to state. The conjecture is the following:
In every base b > 2, there is at least one nontrivial PPDI.
Base (or radix) is the value on which a traditional positional system of number representation is based. In everyday life, we use a decimal or base-10 system of representing integers. Thus, for example, 12310 (i.e, 123 in base-10) represents
1 x 102 + 2 x 101 + 3 x 100 = 100 + 20 + 3
Aside from base-10, the most commonly used systems for representing numbers are binary (base-2), octal (base-8), and hexadecimal (base-16). With a little arithmetic, one may easily verify that
12310 = 11110112 = 1738 = 7B16
(Since base-16 requires 6 more numerals—number symbols—than the 10 we conventionally use, we employ letters to represent values greater than 9. Thus A = 10, B = 11, etc.)

 A number n is a pluperfect digital invariant (or PPDI) in base-b if it is represented in base-b by the digits
dmdm-1dm-2 … d1
and
dmm + dm-1m + dm-2m + … + d1m =  n
We refer to m, the number of digits in the representation of n in base-b, as the order of the PPDI. By a nontrivial PPDI, we mean a PPDI of order greater than 1, since every 1-digit number representation in any base represents a PPDI. (Think about it.)

In case your eyes have glazed over, I will offer a couple of examples to clarify what PPDIs look like. For example, 407 is an order-3 PPDI in base-10 because
43 + 03 + 73 = 64 + 0 + 343 = 40710
Likewise, 1824 is an order-4 PPDI in base-9 because
24469 = 2 x 93 + 4 x 92  + 4 x 91 + 6 x 90 = 1458 + 324 + 36 + 6 = 182410
and
24 + 44  + 44 + 64 =16 + 256 + 256 + 1296 = 182410
PPDIs are not common, but neither are they rare. In base-10, for example, there are 89 PPDIs of orders 1 through 39. (There are no base-10 PPDIs of order greater than 39.)

So let me return to what I will now call the Deimel conjecture:
In every base b > 2, there is at least one nontrivial PPDI.
By exhaustive search, it has been shown that there is at least one PPDI for every base from 2 to 1000. This certainly suggests that the conjecture might be true, but it doesn’t guarantee that there are nontrivial PPDIs in bases 1001 or 56000 or 2894361. In fact, however, we know more. I have proved the following, seemingly odd, theorem:
THEOREM: There is at least one nontrivial PPDI in every base b > 2, except possibly where b = 18k and all the following are true: (1) k is neither a perfect square nor twice a perfect square and (2) neither k-1 nor k+1 is divisible by 5.
Numbers and operators
The strange restrictions seen in this theorem result from the fact that it is possible to show that certain patterns of PPDIs occur in related bases. The simplest such result asserts that any number written as a 1-digit number in a given base is a PPDI. Several 2- and 3-digit PPDIs are the bases of theorems asserting the existence of PPDIs in related, larger bases. Such theorems fail to tell us about, for example, base-90. Using a computer, it has been shown that the smallest PPDI in base-90 is a 8 digits long. It is difficult even to form hypotheses about what PPDIs in larger bases might be implicated by such a representation. Quite possibly, no other PPDI is related to it in a simple way.

Although it is not clear how to prove the Deimel conjecture (or even improve on the theorem offered above), there is an obvious way of going about disproving it. All one has to do is consider all PPDI candidates in base 1001, 1002, etc. (Fortunately, it is easily shown that there is an upper limit to the magnitude of any PPDI in a given base.) In other words, the conjecture can be disproved by exhibiting a counterexample. This procedure has the disadvantage or requiring a lot of computer time, and, if the conjecture is actually true, a counterexample, i.e., a base without nontrivial PPDIs, will never be found no matter how much computing power is thrown at the problem.

I am inclined to suspect that my conjecture is indeed true, but the only evidence I have for that is the lack of a counterexample in light of a good deal of searching for one. I have no idea how to go about proving the conjecture. I challenge the mathematically inclined with nothing better to do to try to prove or disprove the Deimel conjecture. I must offer the disclaimer, however, that I know of no past, present, or future practical use for the result, whatever it may be. Do let me know if you resolve the status of the conjecture.

I treat PPDIs more formally on my Web site. You should go there if you are thinking of tackling this problem. Good luck!

No comments:

Post a Comment

Anonymous comments are not allowed. Gratuitous profanity or libelous statements will be removed. Comments will also be removed that include gratuitous links to commercial Web sites. Please stay on topic.