Because addition and multiplication of two order types are non-commutative operations, we have that for every integer n, given n ordinals, there are at most n! distinct possible values for the sum (or the product) of these n ordinals when all permutations are considered. In fact, A. Wakulic (Fund. Math., XXXVI, pp 255-260) was able to establish the effective function F(n) giving the maximal possible number of distinct values for the SUM of n ordinals, when considering all permutations. QUESTION: What is the effective function G(n) giving the maximal possible number of distinct values for the PRODUCT of n ordinals, when considering all permutations ? Gérard Lang
$\begingroup$
$\endgroup$
2
-
4$\begingroup$ To save other people hunting, Wakulicz paper is matwbn.icm.edu.pl/ksiazki/fm/fm36/fm36126.pdf . The answer for addition (once $n > 20$) is $81^t 193^r$ where $n-1 = 5t+6r$ and $0 \leq r \leq 4$. This is of size roughly $81^{n/5} \approx 2.41^n$, beating the value $2^{n-1}$ obtained by using $\omega$, $\omega^2$, $\omega^3$, ..., $\omega^n$. I have not yet understood Wakulicz's proof. $\endgroup$– David E SpeyerCommented Aug 27, 2014 at 14:18
-
1$\begingroup$ The paper of Wakulicz (pages 255-266) is written in french. The formula valid for n>20 is obtained by writing all ordinals in their Cantor normal form (as a pseudo-polynomial of powers of ω) and analyzing very precisely the consequences of the fact that every term with a power of ω written at the left of another term with a strictly greater power of ω can be eliminated of the sum. So that I do not think that this method can be used in the case of the product. Gérard Lang $\endgroup$– Gérard LangCommented Aug 27, 2014 at 22:46
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Simply take the ordinals $\omega+1,...,\omega+n$ and one obtains $n!$ distinct products (This solution was taken from Chapter 8 Problem 39 and Chapter 9 Problem 66 in the book Problems and Theorems is Classical Set Theory).
This follows from the easily provable fact that for natural numbers $r_{1},...,r_{n}$ we have $$(\omega+r_{1})\cdots(\omega+r_{n})=\omega^{n}+\omega^{n-1}r_{n}+\omega^{n-2}r_{n-1}+...+\omega r_{2}+r_{1}.$$
-
4$\begingroup$ Here's a link to a paper of Erdos where he says (page 128) that this remark is due to Spanier: renyi.hu/~p_erdos/1950-13.pdf $\endgroup$– AshutoshCommented Aug 28, 2014 at 15:06
-
$\begingroup$ Great! This is very clear. $\endgroup$ Commented Aug 28, 2014 at 16:03
-
2$\begingroup$ Erdos's paper also contains a proof of Wakulicz's result. They appeared within a year of each other (Wakulicz first), and neither mentions the other, so presumably independent discovery. Those who prefer English to French, or prefer a quick exposition of the key steps to a long detailed exposition, will probably prefer Erdos's version. $\endgroup$ Commented Aug 28, 2014 at 18:07
-
2$\begingroup$ In fact, Erdôs remarked a slight mistake in Wakulicz's paper, and as this remark was published as a correction of Wakulicz's paper by Erdôs in Fund Math XXXVIII, so that certainly Erdôs knew Wakulicz,s result. Gérard Lang $\endgroup$ Commented Aug 29, 2014 at 16:26
$\begingroup$
$\endgroup$
For a lower-bound partial answer, note that there are at least as many ways to form a product as a sum, and so $F(n)\leq G(n)$. This is because we may replace an ordinal $\alpha$ with $\omega^\alpha$ and thereby turn multiplication into addition via $\omega^\alpha\cdot\omega^\beta=\omega^{\alpha+\beta}$. Since $\omega^\alpha=\omega^\xi$ just in case $\alpha=\xi$, this means that the ordinals $\alpha_1,\ldots,\alpha_n$ have exactly the same number of permuted sums as the ordinals $\omega^{\alpha_1},\ldots,\omega^{\alpha_n}$ have permuted products.
Perhaps the functions for addition and multiplication are simply the same function? I don't see quite yet whether one can get more products by using ordinals not of the form $\omega^\alpha$.
answered Aug 27, 2014 at 10:26