[math-fun] distinct and square-free factorizations
Call a factorization distinct if there are no repeated factors, and call a factorization square-free if it contains no squares. For all positive integers > 1 I claim the number of each match. For example of the sixteen factorizations of 72: A 72 B 8.9 C 6.12 D 4.18 E 3.24 F 3.4.6 G 3.3.8 H 2.36 I 2.6.6 J 2.4.9 K 2.3.12 L 2.3.3.4 M 2.2.18 N 2.2.3.6 O 2.2.2.9 P 2.2.2.3.3 seven (GILMNOP) have repeated factors, and seven (BDFHJLO) contain 4, 9 or 36. Do you know any citation for this? (Assuming it's in fact true!<;-) Also, I'd like to see your proofs, to see how they differ from mine. Particularly interesting would be an explicit construction mapping the factorizations 1-1. (At first I thought this was easy--just split q^2 into q.q--but it's unclear to me what the images of J or P, say, ought to be). Thanks!
Consider one of the factors q of a square-free factorization; suppose it appears d times. Let the binary expansion of d be 2^a1 + 2^a2 + ... + 2^ak Construct a repetition-free factorization by replacing q*q*q...*q with (q^2^a1)*(q^2^a2)*...*(q^2^ak), and similarly for all other factors. Conversely, any factor of a repetition-free factorization can be uniquely written as q^2^a where q is not a square. Collect all factors with the same non-square q as a base, call them q^2^a1, q^2^a2, ..., q^2^ak. Then the a_i are distinct (since the initial factorization is repetition-free), so let d = a1+a2+...+ak and construct a square-free factorization with d copies of q, and similarly for all other non-square bases that appear. J.P. Grossman On Wed, 14 May 2003, Marc LeBrun wrote:
Call a factorization distinct if there are no repeated factors, and call a factorization square-free if it contains no squares. For all positive integers > 1 I claim the number of each match.
For example of the sixteen factorizations of 72:
A 72 B 8.9 C 6.12 D 4.18 E 3.24 F 3.4.6 G 3.3.8 H 2.36 I 2.6.6 J 2.4.9 K 2.3.12 L 2.3.3.4 M 2.2.18 N 2.2.3.6 O 2.2.2.9 P 2.2.2.3.3
seven (GILMNOP) have repeated factors, and seven (BDFHJLO) contain 4, 9 or 36.
Do you know any citation for this? (Assuming it's in fact true!<;-)
Also, I'd like to see your proofs, to see how they differ from mine.
Particularly interesting would be an explicit construction mapping the factorizations 1-1. (At first I thought this was easy--just split q^2 into q.q--but it's unclear to me what the images of J or P, say, ought to be).
Thanks!
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This thing about square-free and distinct factorizations is extremely reminiscent of a result that was discussed on this forum about a decade ago. (Insert obligatory query about archives here.) I remember serving primarily as a listener. If my memory is correct, Gosper told me a similar result: The number of partitions of an integer n into ODD integers equals the number of partitions of the same n into DISTINCT integers. Partitions into odds are analogous (if my intuition is correct) to square-free factorizations; while partitions into distincts are like distinct factorizations in the problem presently under discussion. I will, therefore, digress and discuss the partition problem, returning to factorizations at the end. Consider the case N = 7. Leaving out the plus signs for brevity, partitions of 7 into odd integers are: 7, 511, 331, 31111, 1111111 Partitions into distinct integers are: 7, 61, 52, 43, 421 Note that there are five of each. Somebody noticed, I don't know how, that there are always the same number of both kinds of partitions, regardless of N. Gosper showed me an absurdly intricate _analytic_ proof of this, and bewailed the lack of a _combinatorial_ proof; the latter was discovered later, either by Gosper or by Schroeppel, if memory serves. The analytic proof constructed generating functions from the two sequences, and then showed analytically that the generating functions were equal. Presumably Gosper can reconstruct this proof with less trouble than I, so I will leave it to him. The combinatorial proof shows a direct 1-1 correspondence between partitions of the two types. To convert a partition of the "odd" type to one of the "distinct" type, find a pair of identical piles and merge them. Repeat until there are no identical piles; by construction the resulting partition is of the "distinct" type. The inverse operation is to find an even pile and break it into two equal ones. This operation is repeated until there are no even piles, so the result is a partition of "odd" type. Now that I have typed this out, it is fairly obvious that an analogous argument can be made for distinct and square-free factorizations. A distinct factorization can be converted to a square-free one by repeatedly splitting square factors until none remain; the inverse operation combines identical factors until none remain. QED, sez me. -A
At 03:45 PM 5/15/03, Allan C. Wechsler wrote:
The number of partitions of an integer n into ODD integers equals the number of partitions of the same n into DISTINCT integers.
(All integers positive, of course.) This is Theorem 344 in Hardy & Wright; they give both the generating function and combinatorial proofs. The generating function proof is quite easy. The g.f. for partitions into odd parts is 1/((1-x)(1-x^3)(1-x^5)...) while the g.f. for partitions into distinct parts is (1+x)(1+x^2)(1+x^3)... The latter can be rewritten as (1-x^2)/(1-x) * (1-x^4)/(1-x^2) * (1-x^6)/(1-x^3) * ... The even-exponent terms in the numerators cancel like terms in the denominators; this leaves the odd-exponent terms in the denominators, so the result is the same as the first g.f. -- Fred W. Helenius <fredh@ix.netcom.com>
Nice mapping between odd partitions and distinct partitions. Reminds me of the slick mapping between distinct odd partitions and self-dual partitions. Bend the odd numbers into gnomons and nest them: Distinct odd partition (7, 5, 1) A A AB AB AB AB ABC maps to self-dual partition (4, 4, 3, 2) AB ABC ABBB AAAA ----- Original Message ----- From: Allan C. Wechsler To: math-fun Sent: Thursday, May 15, 2003 3:45 PM Subject: Re: [math-fun] distinct and square-free factorizations [omitted stuff] The combinatorial proof shows a direct 1-1 correspondence between partitions of the two types. To convert a partition of the "odd" type to one of the "distinct" type, find a pair of identical piles and merge them. Repeat until there are no identical piles; by construction the resulting partition is of the "distinct" type. The inverse operation is to find an even pile and break it into two equal ones. This operation is repeated until there are no even piles, so the result is a partition of "odd" type. [more omitted stuff] -A
=Allan C. Wechsler extremely reminiscent of a result that was discussed on this forum about a decade ago.
In fact, recalling this, I'd hoped to retrieve some collective memories!
Gosper showed me an absurdly intricate _analytic_ proof of this, and bewailed the lack of a _combinatorial_ proof;
As others have noted, the classic proof is elegant but not intricate--an Euler hack, from around 1740(?). Actually, it's _symbolic_ rather than _analytic_, entailing only formal manipulations of the generating functions. But arguably my own proof "absurdly" generalized Euler by using vectors as exponents (and similar shenanigans). So I wanted to see what saner alternates others would propose.
the inverse operation combines identical factors until none remain.
Alas I kept missing that "combine" must mean "incrementally, pairwise". Otherwise 2.2.2.2.2.2 and 8.8 might both "combine" into 64. Similarly a subtle issue with the old partition query is that effective conversion procedures from one type to another might still be many-to-one. Fortunately JP Grossman's elegant procedures finally clarified this. Very nice! To bring the thread full-circle: You can specialize this general result to roundaboutly prove the old partition identity, which is equivalent to factorizations of prime powers (ie the "exponent vectors" are scalar).
mlb>In fact, recalling this, I'd hoped to retrieve some collective memories! acw>> Gosper showed me an absurdly intricate _analytic_ proof of this, and
bewailed the lack of a _combinatorial_ proof;
Here are my memories. Unfortunately, the TeX sources appear to to have been abandoned at Xerox PARC. Shortly after the announcement of the factorization of 2^2^2^3+1, I sent a(n unrelated) letter to the the usual gang of maniacs (Dick Askey, George Andrews, George Gasper (I think), Rich&Hilarie, etc.) that began: "Dear Thai food lovers and Rich," answering Hilarie's challenge to find a bijection between the *complements* of the odd partitions and distinct partitions. I.e., pair the not-all-differents with the not-all-odds. A very young Peter Weyhrauch and I came up with one, and then a PARC coworker, Ted Kaehler, came up with a different one! I then found a generalization of the theorem to residue classes mod k, of which #(some evens) = #(some duplicates) was the case k=2. This led to a nonobvious generating function identity. It would be nice to locate a hardcopy of that letter. --rwg
participants (6)
-
Allan C. Wechsler -
David Wilson -
Fred W. Helenius -
JP Grossman -
Marc LeBrun -
R. William Gosper