Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The collection of prime powers can be characterized in the following way:

There is a field with $q$ elements if and only if $q$ is a prime power. Furthermore if it exists then this field is unique up to isomorphism.

My question is,

Is there an analogous characterization for positive integers which are products of two distinct prime powers?

To avoid triviality let us say that the characterization should be presented independently of the prime factorization of the number involved. So we are looking for a statement like,

"There exists a set from a certain class which has property $P(n)$ if and only if $n$ is a product of two distinct prime powers,"

and both the set from the relevant class and the property $P(n)$ should be defined in a way that does not inherently depend on the prime factorization of $n$.

share|improve this question
1  
I suppose products of two fields do not count? –  Emil Jeřábek Jan 12 '12 at 11:10
    
@Emil Jerabek Yes, that is what I was trying to say at the end of the question- I am looking for a characterization which doesn't just come from putting together two prime powers to form a new object. –  Alan Haynes Jan 12 '12 at 11:51
2  
You could classify products of two finite fields as finite commutative unitary rings which have precisely four idempotent elements and which are reduced (i.e. no nilpotent elements). Would a statement of $P(n)$ using this classification of products of two finite fields be acceptable? –  felix Jan 12 '12 at 13:15
1  
Every abelian group of order n is cyclic, but there is no field of order n? –  Matt Brin Jan 12 '12 at 13:53
4  
This is a bit tangential, but where is it extremely useful that prime powers are chatacterized in the way given in the answer? To make more precise what I mean, of course it is useful to have a sort of complete description of finite fields. And, I also would know why it is useful that say primes are chatacterized by the fact that Z/nZ is a field. But why this characterization of prime powers is useful I would not know. –  quid Jan 12 '12 at 15:12

4 Answers 4

For any (first order, but other variants are also reasonable) formula $\varphi$ without free variables, finite model theory defines $S(\varphi)$, the "spectrum" of $\varphi$, as the set of all positive natural numbers $n$ such that there exists a structure of size $n$ satisfying $\varphi$.

(As far as I remember, there is no nice characterization of those subsets of $\mathbb N$ which are spectra. In particular: it is still open whether the set of all spectra of first order formulas is closed under complements.)

It would be reasonable to define $S^*(\varphi)$ as the set of all $n$ such that there is a unique (up to isomorphism) structure of size $n$ satisfying $\varphi$.

As Emil Jeřábek has implicitly pointed out in his first comment, there is a first order formula $\varphi_{\text{product of fields}} $ such that $S^*(\varphi_{\text{product of fields}} )=S(\varphi_{\text{product of fields}} ) = $ the set of all products of two prime powers. (The formula is really quite explicit; I do not give it here as it would not add any relevant information to my answer, I think.)

I know that this answer is in a sense trivial. But I don't see a formal criterion that will distinguish the trivial from the nontrivial answers.

share|improve this answer
1  
As Martin says there is still much we do not know about spectra. A very recent paper on the subject is "Spectra and systems of equations", by Bell, Burris and Yeats, in "Model theoretic methods in finite combinatorics", AMS, Contemporary mathematics, vol 558 (2011), 43-96. –  Andres Caicedo Jan 12 '12 at 15:51
1  
The paper also mentions a survey, "Fifty years of the spectrum problem", Durand, Jones, Makowsky, More. A preprint can be found here: www.diku.dk/hjemmesider/ansatte/neil/SpectraSubmitted.pdf –  Andres Caicedo Jan 12 '12 at 15:53
    
@Goldstern Of course, it is a model theory problem. It sounds like what you are saying is that you can't think of a model for the set described above, besides the collection of pairs of finite fields with different characteristic- neither can I. The "product of two fields" is a misleading name- it's not a field, and however you define it, it's not intrinsically different than saying the number is a product of two prime powers. Felix's idempotent description is closer to the kind of model I am looking for, but still depends too intrinsically on the prime factorization. –  Alan Haynes Jan 12 '12 at 16:02
1  
There is a very nice characterization of sets that are (first-order) spectra: exactly those that are computable in NE (nondeterministic exponential time), where $n$ is given in binary. –  Emil Jeřábek Jan 12 '12 at 16:14
1  
@AH: I agree that my description is not intrinsically different from saying that $n$ is a product of two prime powers. But do you have a mathematical definition of this concept of "intrinsically different"? –  Goldstern Jan 14 '12 at 9:10

If nothing else then $n$ is a product of powers of two distinct primes iff there is a unique pair of relatively prime natural numbers, other than the trivial $\lbrace 1,n \rbrace$, whose product is $n$.

share|improve this answer

There are at most 2 groups (up to isomorphism) of order $n$, and there is not a field of order $n$, if and only if $n$ is the product of two distinct primes.

This doesn't cover "prime powers", but at least it's nontrivial.

share|improve this answer

A natural number $n$ is the product of precisely two prime powers if and only if there exists an abelian group of order $n$ having precisely two maximal subgroups. (And that group is unique up to isomorphism.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.