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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

The classification of groups of order $n$

Answer 4

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.

Answer 5

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)$).

Answer 6

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).

Answer 7

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.

Answer 8

Convex Equipartitions of volume and surface area.

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.

Answer 9

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.