# What are examples of problems we know how to solve for primes (or prime powers), but not for composites?

I am interested in seeing examples of research problems which fall into one of the two following categories:

1. A problem which is solved in the case of primes (or prime powers), but which remains open in the case of composite integers.

2. A problem which historically was first solved for primes, and then significant additional work was needed to prove the result for all integers.

This is a rather broad question, so I'm mainly interested in combinatorial or algebraic problems that appear to be easy over primes because of the existence of certain structures which exist for primes, but not for all integers (e.g., for any prime power $$q$$, there is a finite field $$\mathbb{F}_q$$ of size $$q$$, but there is no finite field of size $$6$$).

An example of the sort of problem I'm looking for in the first category is tesselations of integers. We say a finite set $$A$$ of integers is a "tile" if there exists an infinite set of integers $$X$$ such that for every integer $$n$$, the equation $$n = a +x$$ has exactly one solution $$(a,x)\in A\times X$$. In the 70s, Newman showed that for any prime power $$q$$, there is a simple characterization for the set of tiles $$A$$ of size $$q$$. Additional work has characterized the possible tile sets $$A$$ when $$|A|$$ has very few distinct prime factors, for example, but in general characterizing the possible tile sets of size $$n$$ for an arbitrary integer $$n$$ remains open.

• The topological Tverberg problem and cousins (graph evasiveness conjecture, etc.) where group cohomological methods come into play. Commented Feb 2, 2023 at 19:22
• The existence of a q-ary $(4, q^2, 3)$ code is fairly simple to show for prime power $q\neq 2$, but it was once an open problem for general values of q. In general I believe there are other problems in coding theory which are fairly easy when you can use linear codes but hard for other values. Commented Feb 2, 2023 at 20:22
• Another example from coding theory - the Gilbert-Varshamov bound is much weaker for non-prime-power q. Commented Feb 2, 2023 at 20:28
• Does factoring count? It is very quick and easy for prime powers, but hard and slower in general. Commented Feb 2, 2023 at 21:34
• Almost an answer: the Casas-Alvero conjecture is known when the degree is of the form $dp^r$ for $d \leq 7$ and $p$ prime (for $3 \leq d \leq 7$, there are finitely many primes $p$ that have to be excluded). Commented Feb 3, 2023 at 14:49

## 9 Answers

There is a projective plane of order $$N$$ for every prime power $$N$$. The existence of projective planes of other orders is an open question; in particular, it is not known whether there is a projective plane of order $$12$$. See, e.g., https://en.wikipedia.org/wiki/Projective_plane#Finite_projective_planes

• However, note that even for prime powers, it is unknown whether there are any other projective planes.
– aorq
Commented Feb 3, 2023 at 15:40

Regarding Option 2 in the question:

"A primitive permutation group of degree $$n$$ containing a cycle of prime length $$2\le p \le n-3$$ must be the alternating or symmetric group."

This is a famous theorem by Jordan from the 1870s. It took a century to obtain that "prime" can be relaxed to "prime power", and afterwards it took the classification of finite simple groups to find out that the word "prime" can be dropped altogether, see

Peter M. Neumann, Primitive Permutation Groups Containing a Cycle of Prime-Power Length, Bulletin of the London Mathematical Society 7 (3), 1975, 298–299,

G. Jones, Primitive permutation groups containing a cycle, Bulletin of the Australian Mathematical Society, 89(1), 2014, 159-165.

The classification of groups of order $$n$$

• Have finite simple groups not been classified for arbitrary order (not just prime)? Commented Feb 3, 2023 at 17:24
• I never said anything about simplicity. Commented Feb 3, 2023 at 17:47
• Groups of prime order have certainly been classified, but prime power order, not so much. Commented Feb 3, 2023 at 21:03
• @GerryMyerson: True, but the OP said "A problem which is solved in the case of primes (or prime powers)" - in this case, it is solved for the primes. Commented Feb 3, 2023 at 22:02
• Even though not stated like that, I would at least do the OP the favor to interpret the question as "a problem that's solved, but not entirely banal for...", or "a problem for whose proof primality helps without completely trivializing it". Commented Feb 4, 2023 at 4:15

A problem which historically was first solved for primes, and then significant additional work was needed to prove the result for all integers.

The existence of infinitely many Ramanujan graphs of degree $$n+1$$ was proven for prime $$n$$ by Lubotzky, Philips, and Sarnak and for arbitrary $$n$$ 27 years later by Marcus, Spielman, and Srivastava.

This didn't just require additional work - the method was completely different, with virtually no overlap in ideas.

Everything related to the computational difficulty of factorizing integers should give you an answer. For instance, it is computationally easy to compute Euler's totient function for powers of primes, but it is computationally difficult to compute it for arbitrary integers. As a consequence, it is trivial to produce a generator of a multiplicative group of prime order (any nontrivial element would do), but it is computationally very difficult to produce a generator of the multiplicative group of $$\mathbb Z / n \mathbb Z$$ for composite $$n$$ (because its order is $$\varphi (n)$$).

• Another example: taking square roots mod $n$ can be done efficiently if $n$ is prime, but if $n$ is composite and you don't know the factorization, then there is no known computationally efficient method. Commented Feb 4, 2023 at 21:54

Problem 105b in Chapter 1 of Richard Stanley's Enumerative Combinatorics, Volume 1 (2nd edition) notes that if $$n$$ is odd, then the number of necklaces (up to cyclic rotation) with $$n$$ beads, each bead colored black or white, is $${1\over n} \sum_{d|n \atop d\,\rm odd} \phi(d)\,2^{n/d}.$$ The problem is to give a combinatorial proof of this fact. This is easy when $$n$$ is prime, but I think it is still open in general (or even if it is not, the composite case is certainly much more difficult).

Classification of Hopf algebras of a given dimension in characteristic 0. For primes, see Hopf algebras of prime dimension by Yongchang Zhu and Hopf algebras of prime dimension in positive characteristic by Siu-Hung Ng and Xingting Wang for other characteristic.

We show that, for any prime power $$p^k$$ and any convex body $$K$$ (...) in $$\mathbb{R}^d$$, there exists a partition of $$K$$ into $$p^k$$ convex sets with equal volume and equal surface area.

I believe the (or at least one) source here is a MathOverflow question by Nandakumar.

• Could you link the question? Commented Feb 3, 2023 at 23:33
• I have been unable to locate the MO question by Nandakumar. Commented Feb 3, 2023 at 23:43
• Are you perhaps thinking of this question? On 'fair bisectors' of planar convex regions. Commented Feb 4, 2023 at 22:00

The Alon–Tarsi conjecture says that if $$n$$ is even, then the number of even Latin squares is different from the number of odd Latin squares (where the parity of a Latin square can be defined as the product of the parities of its rows and columns, considered as permutations). It is known in special cases, in particular when $$n = p\pm 1$$, but is open in general. The proof techniques for $$n=p\pm 1$$ make use of special properties of primes. For example, Drisko's proof of the case $$n=p+1$$ uses the Sylow theorems; in the Sylow theorems, you cannot simply replace the prime $$p$$ with an arbitrary integer.