4
$\begingroup$

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

$\endgroup$
15
  • 1
    $\begingroup$ I suppose products of two fields do not count? $\endgroup$ Jan 12, 2012 at 11:10
  • $\begingroup$ @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. $\endgroup$ Jan 12, 2012 at 11:51
  • 2
    $\begingroup$ 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? $\endgroup$
    – felix
    Jan 12, 2012 at 13:15
  • 1
    $\begingroup$ Every abelian group of order n is cyclic, but there is no field of order n? $\endgroup$
    – Matt Brin
    Jan 12, 2012 at 13:53
  • 4
    $\begingroup$ 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. $\endgroup$
    – user9072
    Jan 12, 2012 at 15:12

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 12, 2012 at 15:51
  • 1
    $\begingroup$ 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 $\endgroup$ Jan 12, 2012 at 15:53
  • $\begingroup$ @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. $\endgroup$ Jan 12, 2012 at 16:02
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 12, 2012 at 16:14
  • 1
    $\begingroup$ @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"? $\endgroup$
    – Goldstern
    Jan 14, 2012 at 9:10
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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