The first two mathematical conjectures that I describe in this post go back to the days when I was studying math at the University of Copenhagen. At that time I always had several "mathematical pet projects" that I was thinking about whenever I could find some free time. Usually my projects were generalizations of math problems from my classes, and most of them involved number theory, group theory or combinatorics. The two conjectures below are probably the ones that I have thought about for the longest time, and I must admit that it annoys me a bit that I still don't know the answer to any of them.

1. Adding without carry

This conjecture is a generalization of a problem from a math competition. I can't remember the name of the competition at the moment (and in case you are wondering: No, I did not participate in the competition).

Given three positive integers m, n, b  with b>1, is it possible to find a positive integer k such that the addition of mk and nk in base b produce no carries at any place?

As an example, take b=10, m=19, n=17: Obviously, if you add m and n, you will get a carry in place 1, so k=1 will not work. Now, if you take k=3, the addition becomes 57 + 51, with a carry in place 2, so that does not work either. With k=13 however, the addition becomes 247 + 221 with no carries at all, so in this case it is possible to find such a k.

Lets use the shorthand notation S(m, n; b) for the statement: "There exist a positive integer k such that the addition of mk and nk in base b produce no carries at any place."  As we saw in the example above, the statement S(19, 17; 10) is true.

Here are a few easily verifiable facts:

• Let d be a positive integer, then S(m, n; b) is true if and only if S(md, nd; b) is true.
• If gcd(m+n, b) = 1, then S(m, n; b) is true.
• If gcd(m, n) = 1 and b divides m+n, then S(m, n; b) is false.

Gimme proof!

In our quest to determine which triples (m, n, b) makes the statement S(m, n; b) true, the first fact helps us to reduce the problem to triples with gcd(m, n) = 1, and the two other facts solves the problem if b is prime; in that case b either divides m+n or is coprime to m+n, and so the truth-value of S(m, n; b) is fully determined.

This analysis - along with a lot of computation - leads me to the following conjecture:

Conjecture: Assuming gcd(m, n) = 1, the statement S(m, n; b) is true exactly if b does not divide m+n.

I have not been able to find a proof of (or a counter-example to) this conjecture. In fact, I have not been able to determine the correctness of the conjecture for any single composite value of b. If you have any idea about how to proceed, please feel free to send me a message.

However, I have found a justification for the conjecture; I have found an algorithm that will give a value of k — assuming it stops! The algorithm can start exactly if b does not divide m+n, but I have not yet been able to prove that it always stops. I have written a description of the algorithm here.

2. Groups with identical normal subgroup structure

I arrived at this conjecture by a very circuitous route: I actually started out with a problem in calculus! As I tried to solve this problem, it transformed into a combinatorial problem. When I had solved the combinatorial version of the problem, I realized that I could generalize the problem to a problem in group theory, which led to the study of the structure denoted Fu(G) below. When I get the time I may write about this in more detail; the original problems were actually quite interesting!

Let G be a finite group. I define the normal subgroup structure (or just  normal structure) of G to be a graph, the nodes of which are the normal subgroups of G (including G and the trivial subgroup), with an edge from one node to another if one of the corresponding subgroups is contained in the other. Furthermore, each node is labelled with the order of the corresponding subgroup.

Two groups are said to have identical normal subgroup structure if there exists a graph-isomorphism from the graph of one group to the graph of the other, preserving the labelling of the nodes.

For example, the dihedral group of eight elements and the quaternion group have the same normal structure.

To state the promised unsolved problem, we need one more definition: The functional semigroup of G, Fu(G), is defined as the set of functions on G of the form:

x  →  g₀ x g₁ x ... x g_n,

where n is a non-negative integer and g₀, g₁, ..., g_n are elements of G. You can say that Fu(G) is the set of functions of "polynomial form" on G. It should be obvious that Fu(G) is a semigroup with respect to functional composition.

Without further ado, here is my unsolved conjecture:

Conjecture: Two finite groups, G and H, have identical normal subgroup structure if and only if the semigroups Fu(G) and Fu(H) are isomorphic.

The "if" part of the conjecture is actually pretty simple; it is possible to reconstruct the normal structure of G from Fu(G). The "only if" part has eluded me for some time now (as far as I remember I came up with the conjecture in 2001), but I do have some justification for it. One such justification is the following (somewhat surprising) proposition:

Proposition 1. Let G be a finite non-abelian simple group, then Fu(G) is the set of all functions on G.

I don't believe you. Convince me!

From the proposition we see that two non-isomorphic non-abelian simple groups of the same order have isomorphic functional semigroups - and two such groups obviously have identical normal structure.

Another justification is the dihedral groups of order 2ⁿ, n>2 and the generalized quaternion groups. Each dihedral group has identical normal structure to the generalized quaternion group of the same order, and their semigroups are isomorphic.

Another interesting question is: What can be said about G from its normal structure alone? It is not hard to see that it can be determined whether G is abelian, nilpotent, solvable or simple, and it is possible to identify the Frattini subgroup Phi(G) and the largest nilpotent normal subgroup F(G). It is not, however, in general possible to identify the center of G, and as we have seen, it is not always possible to identify the isomorphism class of G.

3. A combinatorial sum related to the queens puzzle (solved)

One of my colleagues asked me about the Eight Queens Puzzle,which prompted me to write some javascript code to solve the puzzle (also for board sizes other than 8x8). Thinking about the puzzle, I realized that I have never seen a proof that the puzzle is solvable for all board sizes greater than 3x3. This led me to thinking about how to prove it, and that again led me to thinking about this set: Q(p) = { (i,j) : i < j ∧ |i - j| = |p(i) - p(j)| }, where p is a permutation of the numbers {1, 2, ..., n}. When this set is empty, the permutation p describes a solution to the puzzle by placing the queens at the positions(i, p(i)) for i = 1, 2, ..., n.

Just for the fun of it, I tried to calculate the sum of the number of elements in the sets Q(p) for all permutations p of order n. For the first few values of n I got:

When you have a sequence like that, and you want to find a formula for it, the first thing you do is look it up at The Online Encyclopedia of Integer Sequences.

This is what I found: A097971. Apparently, this sequence is also the number of alternating runs in all permutations of order n, and it can be expressed as n! (2n-1)/3. This is of course not a proof that my sum can also be expressed by this formula, so I set out to find a proof. First, just to check the result from the OEIS, I proved the formula forthe sum of alternating runs. This was not difficult; there is a fairly simple proof by induction. This strategy does not seem to work with my sum, though; I can't find a good way to apply induction to the problem.

So this is another conjecture that I still haven't found a proof of, though this one seems easier than the others:

Conjecture: ∑_{p ∈ S(n)} |{ (i,j) : i < j ∧ |i - j| = |p(i) - p(j)| }| = n! (2n-1)/3, for n > 1.

Added 2010-11-15: I was perhaps a bit fast to add this problem to my list of unsolved conjectures; the day after I wrote about it, I realized that it was not as hard as I first assumed. I guess I got stuck trying to find a proof by induction, when in fact a proof by "writing down the sum in a different way" was the way to go.

Instead of first summing over all permutations, and then for each permutation counting the number ofpairs (i, j) such that |i - j| = |p(i) - p(j)|, we first sum over all sets of pairs (i, j), (k, l), such that i < j and |i - j| = |k - l|, and then count the number of partitions p for which p(i) = k and p(j) = l. Obviously, since we are just fixing two elements, there are exactly (n-2)! permutations that fulfill this independent of i, j, k and l. The number of quadruples (i, j, k, l) with k < l that fulfill the criteria is equal to the number of those with k > l, so we can restrict our sum to those with k < l, and remember to multiply by 2. Given i and k, the number of pairs (j, l)with i < j ≤ n, k < l ≤ n and |i - j| = |k - l|is min(n - i, n - k), so now the sum can be written:

2 (n-2)! ∑_{1 ≤ i ≤ n}∑_{1 ≤ k ≤ n} min(n - i, n - k)

Now we replace i and k with n - iand n - k, and change the bounds of the sums accordingly. Furthermore, we split the sum in three parts; one for when i = k, one for when i < k and one for when i > k. The last two parts of the sum are equal, so all in all we get:

2 (n-2)! (∑_{0 ≤ i < n} i + 2∑_{0 ≤ i < n}∑_{0 ≤ k < i} k)

Using the formulas ∑_{1 ≤ x ≤ m} x = m(m+1)/2 and ∑_{1 ≤ x ≤ m} x² = m(m+1)(2m+1)/6, the expression reduces to n! (2n - 1)/3 as expected.