Symmetric functions: Kronecker product over any ring; Kronecker coproduct; antipode over any ring; forgotten basis over any ring; Witt basis; Frobenius and Verschiebung; doc fixes

[darij]

This ticket does the following:

1. The current version of itensor (the Kronecker product on the ring of symmetric function) only works when the ground ring is an algebra over the rationals. This is not a mathematically reasonable restriction. Fix this.

2. The Kronecker coproduct on the ring of symmetric function has to be implemented. Implement it.

3. The antipode on the ring of symmetric functions uses coercion into the powersum basis. This means it, too, is not getting computed over arbitrary base rings. Fix this.

4. The forgotten basis of Symm is defined by duality rather than by explicit formulas. Our duality methods use the powersum basis, again leading to errors for ground rings not being QQ-algebras.

5. The Witt symmetric functions form another basis of Symm. Implement them.

6. Implement Frobenius and Verschiebung operations on Symm without recourse to plethysm.

Apply:

• trac_14775-the_big_crunch.patch​

[darij]

3 is done. Anyone has a better name than degree_negation for the algebra automorphism of SymmetricFunctions? which acts as 1 in even degrees and 0 in odd ones?

The changes in the antipode method not only made it work over any rings, but also sped it up on each basis except for the powersum one (and the monomial one, but I improved that with a trivial fix):

Test suite:

def testall():
    Sym = SymmetricFunctions(QQ)
    print "m"
    timeit("SymmetricFunctions(QQ).m()([4,3,2]).antipode()")
    print "h"
    timeit("SymmetricFunctions(QQ).h()([4,3,2]).antipode()")
    print "e"
    timeit("SymmetricFunctions(QQ).e()([4,3,2]).antipode()")
    print "s"
    timeit("SymmetricFunctions(QQ).s()([4,3,2]).antipode()")
    print "p"
    timeit("SymmetricFunctions(QQ).p()([4,3,2]).antipode()")

Results:

original version:

sage: testall()
m
125 loops, best of 3: 1.86 ms per loop
h
25 loops, best of 3: 10.8 ms per loop
e
25 loops, best of 3: 10.8 ms per loop
s
25 loops, best of 3: 30.6 ms per loop
p
625 loops, best of 3: 146 µs per loop

after change of generic antipode to go via omega rather than via coercion to powersum basis:

sage: testall()
m
125 loops, best of 3: 2.16 ms per loop
h
125 loops, best of 3: 2.92 ms per loop
e
125 loops, best of 3: 2.92 ms per loop
s
625 loops, best of 3: 250 µs per loop
p
625 loops, best of 3: 148 µs per loop

after microoptimization in the antipode of powersum (replacing (-1)**blah by case distinction):

sage: testall()             
m
125 loops, best of 3: 1.79 ms per loop
h
125 loops, best of 3: 2.88 ms per loop
e
125 loops, best of 3: 2.95 ms per loop
s
625 loops, best of 3: 252 µs per loop
p
625 loops, best of 3: 113 µs per loop

[darij]

speed tests before and after goal 4 implementation on partition [4,3,2]

[darij]

speed tests before and after goal 4 implementation on partition [4,3,2,2]

[darij]

New version up, with forgotten functions working over every base ring. I've attached two files which show some timings for conversions from and to f. The times over a base ring which is a QQ-algebra have become a tad worse, although probably not significantly (what are our criteria for that?). The times over a base ring which is a QQ-algebra differ significantly from those over a base ring which is not, although not in a sufficiently consistent way for me to prefer one method over the other.

In other news, this patch has profited much from input by Nicolas Thiery, Mike Zabrocki, Florent Hivert and Simon King. Thank you!

[darij]

backup version, implementing goals 1, 2, 3, 4 of 5

[darij]

If anyone could comment on my witt.py file in trac_14775-symmetric_functions_extended-dg.patch​, I'd be much indebted (while the coercions seem to work, my understanding of OOP is still very fragmentary and I wouldn't be surprised if some of what I've done is bad practice). I am going to add more doctests, implement coercions/conversions to power sums and elementary symmetrics. (And if I really have too much time on my hand, I'll add Frobenius and Verschiebung maps.)

[darij]

While there are good formulas for the h, e, p bases in terms of the w bases, as well as not-too-slow algorithms for the w basis in terms of the h, e, p bases (basically by inverting the formulas just mentioned), I am not sure which of them I should implement. Right now I have implemented h-to-w and w-to-h, declaring them as coercions, and p-to-w. The h-to-w and w-to-h coercions use a cache like the ones in dual.py. Now I need guidance on the following:

1) Is it a good idea to also use cache for e-to-w and w-to-e? (The downside is that there will be more caches in memory.) Same for p-to-w (my current implementation is cacheless, thus not as fast as it could be) and w-to-p.

2) If I implement these maps, should I register them as coersions? (This would normally make sense, but I fear they could significantly slow down coercions between standard classical bases because of the asinine way the current system generates coercion paths.)

[aschilling]

Hi Darij,

Could you run some benchmarks to check what happens when you implement and register the above mentioned coercions?

Anne

[nthiery]

Replying to darij:

1) Is it a good idea to also use cache for e-to-w and w-to-e? (The downside is that there will be more caches in memory.) Same for p-to-w (my current implementation is cacheless, thus not as fast as it could be) and w-to-p.

Only practice will tell, and you'll probably be the one putting this most to practice; I'd say don't cache for now, and see later if you need it.

And at some point in the future we would want a mechanism that would allow the user to specify which caches he want to use for his own preferred application.

2) If I implement these maps, should I register them as coersions? (This would normally make sense, but I fear they could significantly slow down coercions between standard classical bases because of the asinine way the current system generates coercion paths.)

Go ahead. For most classical basis, Symmetrica provides a direct conversion, and when there is one the coercion system is not as stupid as using his depth first search :-)

In any case, if something would need to be fixed, it's the coercion system, not the usage of coercions as above.

Cheers,

Nicolas

[darij]

Uploading a new version, mostly with docstring fixes. Thanks for your replies, Anne and Nicolas; I'll work on this shortly (haven't returned to the Witt symmetric functions yet).

[darij]

Done!

@Anne: I've run some benchmarks (which show that caching the coercions to all of the h, e and p bases is a lot better than caching only the one to the h basis). But they don't mean very much since Sage, in the absence of a direct coercion, looks for a compound coercion by depth-first search (which can be, and is in my case, extremely slow). I was too lazy to manually register 2-step coercions, so I went a different way and gave the user the freedom to decide what coercions to cache.

In other news, this patch probably conflicts with every other patch that edits symmetric functions -- sorry.

[darij]

Finished; please review!

[darij]

If you are wondering about the latest change: I removed an obsolete TODO which was already done. Sorry for that being in the patch in the first place.

[aschilling]

@Anne: I've run some benchmarks (which show that caching the coercions to all of the h, e and p bases is a lot better than caching only the one to the h basis). But they don't mean very much since Sage, in the absence of a direct coercion, looks for a compound coercion by depth-first search (which can be, and is in my case, extremely slow). I was too lazy to manually register 2-step coercions, so I went a different way and gave the user the freedom to decide what coercions to cache.

Darij, could you post the results of your benchmarks?

[darij]

Here's one:

sage: Sym = SymmetricFunctions(QQ)
sage: Sym.inject_shorthands()
/home/darij/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/combinat/sf/sf.py:1174: RuntimeWarning: redefining global value `e`
  inject_variable(shorthand, getattr(self, shorthand)())
sage: w = Sym.w()
sage: timeit("h(w[4,3,2,1])")
5 loops, best of 3: 105 µs per loop
sage: timeit("w(h[4,3,2,1])")
625 loops, best of 3: 103 µs per loop
sage: timeit("e(w[4,3,2,1])")
5 loops, best of 3: 75.5 ms per loop
sage: timeit("w(e[4,3,2,1])")
5 loops, best of 3: 3.26 ms per loop
sage: timeit("s(w[4,3,2,1])")
5 loops, best of 3: 67.6 ms per loop
sage: timeit("w(s[4,3,2,1])")
125 loops, best of 3: 1.73 ms per loop
sage: timeit("p(w[4,3,2,1])")
25 loops, best of 3: 8.5 ms per loop
sage: timeit("w(p[4,3,2,1])")
125 loops, best of 3: 1.88 ms per loop
sage: 
sage: w = Sym.w(coerce_h=False, coerce_p=True)
sage: timeit("h(w[4,3,2,1])")
5 loops, best of 3: 45.4 µs per loop
sage: timeit("w(h[4,3,2,1])")
625 loops, best of 3: 102 µs per loop
sage: timeit("e(w[4,3,2,1])")
5 loops, best of 3: 75.9 ms per loop
sage: timeit("w(e[4,3,2,1])")
5 loops, best of 3: 1.86 ms per loop
sage: timeit("s(w[4,3,2,1])")
5 loops, best of 3: 67.4 ms per loop
sage: timeit("w(s[4,3,2,1])")
5 loops, best of 3: 1.63 ms per loop
sage: timeit("p(w[4,3,2,1])")
625 loops, best of 3: 96.1 µs per loop
sage: timeit("w(p[4,3,2,1])")
625 loops, best of 3: 95.9 µs per loop
sage: 
sage: w = Sym.w(coerce_h=False, coerce_e=True)
sage: timeit("h(w[4,3,2,1])")
5 loops, best of 3: 246 ms per loop
sage: timeit("w(h[4,3,2,1])")
625 loops, best of 3: 1.51 ms per loop
sage: timeit("e(w[4,3,2,1])")
625 loops, best of 3: 88.5 µs per loop
sage: timeit("w(e[4,3,2,1])")
625 loops, best of 3: 87.3 µs per loop
sage: timeit("s(w[4,3,2,1])")
25 loops, best of 3: 9.33 ms per loop
sage: timeit("w(s[4,3,2,1])")
625 loops, best of 3: 1.09 ms per loop
sage: timeit("p(w[4,3,2,1])")
5 loops, best of 3: 95.4 ms per loop
sage: timeit("w(p[4,3,2,1])")
625 loops, best of 3: 1.52 ms per loop
sage: 
sage: w = Sym.w(coerce_h=True, coerce_e=True, coerce_p=True)
sage: timeit("h(w[4,3,2,1])")
5 loops, best of 3: 117 µs per loop
sage: timeit("w(h[4,3,2,1])")
625 loops, best of 3: 103 µs per loop
sage: timeit("e(w[4,3,2,1])")
5 loops, best of 3: 94 µs per loop
sage: timeit("w(e[4,3,2,1])")
625 loops, best of 3: 88.2 µs per loop
sage: timeit("s(w[4,3,2,1])")
5 loops, best of 3: 67.6 ms per loop
sage: timeit("w(s[4,3,2,1])")
5 loops, best of 3: 1.47 ms per loop
sage: timeit("p(w[4,3,2,1])")
625 loops, best of 3: 96.8 µs per loop
sage: timeit("w(p[4,3,2,1])")
625 loops, best of 3: 96.6 µs per loop

It's fun how s(w) is quickest with the e-coercion but the advantage disappears when all three coercions are on (because it doesn't know where to go)...

[darij]

for the patchbot:

apply trac_14775-symmetric_functions_extended-dg.patch

[tscrim]

Hey Darij,

Here's a review patch which is basically just formatting changes and compacts the implementation of degree_negation(). If you're happy with my changes, you can set this to positive review.

Best,
Travis

[darij]

Here's a review of your review. Thanks for the formatting changes which I should have done myself (do you know of a good way to automatically cut the docstring lines to the length they should have, whatever that length is?). Nice work on degree_negation. Most of what I'm fixing in my review is not your errors but mine or old ones.

One thing I've reverted from your review which doesn't seem accidental is "there is no canonical choice for a basis"; this was an abuse of the notion of "canonical". All of the classical bases of Sym are canonical in the sense of category theory (which means "functorial in the ground ring"), and that's really the only formal meaning of this notion in mathematics. Apparently "canonical" was meant as "clearly more natural than the others", but that's imprecise and subjective. IMHO "it does not come with a basis already chosen" reflects better what is happening.

[darij]

additional method for arithmetic product

[darij]

I've just added a new attachment trac_14775-addendum_arith_prod-dg.patch​ with a new method for the arithmetic product ( ​http://mathoverflow.net/questions/138148 ). Sorry for straining you more, Travis; if you wish, I can move this to a new ticket.

So far, for the patchbot:

apply trac_14775-symmetric_functions_extended-dg.patch trac_14775-review-ts.patch trac_14775-rereview-dg.patch​ trac_14775-addendum_arith_prod-dg.patch

[tscrim]

Hey Darij,

Sorry I didn't get back to you yesterday. I don't like the phrasing you used (and canonical to me means there is a clear/special reason why this basis is "better" than the others). How about something like

1 - "there is no natural choice for a basis",

2 - "there are multiple natural bases"?

Looking at the arithmetic product (which should go here I think), I have some suggestions:

• The math equation on line 2842, could you set it in a .. MATH:: block?
• I think the OUTPUT block should be a sentence (it really just needs to be capitalized and have a period).
• Remove the else on line 2929 since it makes the code more clear (at least to me since the function ends on the same indent level it started at; and do the de-indent of course).
• Remove some of the comments, in particular the ones describing the variables in the for loops since they are cluttering up the code IMO.

Last, could you fold all of the patches into a single patch? This will make it easier for me to do the final review.

Thank you,
Travis

[darij]

qfold of the previous patches + the changes you suggested

[darij]

Hi Travis,

agreeing with phrasing 2 and all the suggestions. Done!

Best regards,
Darij

patchbot:

apply trac_14775-qfolded.patch​

[tscrim]

Looks good to me now. Thanks Darij.

[darij]

Thanks for reviewing this monster!!

[tscrim]

I noticed a minor docstring problem I missed (and introduced). Here's a small review patch which does the necessary tweak.

For patchbot:

Apply: trac_14775-qfolded.patch​, trac_14775-docstring_tweak-ts.patch

[jdemeyer]

PDF documentation doesn't build:

! Undefined control sequence.
<argument> ...imits _{i \geq 1, j \geq 1} p_{\lcm 
                                                  (\lambda _i, \mu _j)}^{\gc...
l.82512 \end{gather}

? ]]
! Emergency stop.
<argument> ...imits _{i \geq 1, j \geq 1} p_{\lcm 
                                                  (\lambda _i, \mu _j)}^{\gc...
l.82512 \end{gather}

!  ==> Fatal error occurred, no output PDF file produced!
Transcript written on combinat.log.
 [8make[1]: *** [combinat.pdf] Error 1

[darij]

IMHO this is more an issue with the PDF docbuilder... \gcd and \lcm are standard commands.

Does it build fine with trac_14775-operatorname.patch​? I can't check docbuild pdf at all on my system.

[darij]

updated (typo fixed)

[jdemeyer]

Needs review (not my job, sorry...)

[tscrim]

Here's a new version of my tweak patch which builds the pdf:

Build finished.  The built documents can be found in /home/travis/sage-5.11.rc0/devel/sage/doc/output/pdf/en/reference/combinat

Darij, unfortunately \lcm and \gcd are actually not standard latex commands (as counter-intuitive as it is). ​See here. I changed them instead to \mathrm{lcm} and made another tweak that was causing the pdf builder to fail. If you're happy with my changes, go ahead and set this to positive review.

Best,
Travis

[darij]

Thanks and good work finding the typos!

[zabrocki]

I have a couple of comments before the final positive review

• I ran pyflakes and found (some of these could be from previous patches)

  sage/combinat/sf/elementary.py:236: redefinition of unused 'Partition' from line 21
  sage/combinat/sf/powersum.py:334: redefinition of unused 'Partition' from line 21
  sage/combinat/sf/powersum.py:456: redefinition of unused 'Partition' from line 21
  sage/combinat/sf/schur.py:433: 'Partition' imported but unused
  sage/combinat/sf/sfa.py:802: local variable 'result' is assigned to but never used
  sage/combinat/sf/sfa.py:2916: 'Partitions' imported but unused
  sage/combinat/sf/sfa.py:2917: 'divisors' imported but unused
  sage/combinat/sf/witt.py:20: 'classical' imported but unused
  sage/combinat/sf/witt.py:22: 'QQ' imported but unused
  sage/combinat/sf/witt.py:22: 'ZZ' imported but unused
  sage/combinat/sf/witt.py:1309: redefinition of unused 'Integer' from line 22
  

• in the documentation of verschiebung in witt.py line 1294 and elementary.py line 223 and powersum.py line 443 :

same result as the implementation in sfa.py on the monomial

The tests seem to be on complete homogeneous. Is monomial a typo?

• There are a number of whitespace issues in the files that I looked at (e.g. witt.py, dual.py). Please check these carefully.
• for the method frobenius add a ... SEEALSO: :meth:`plethysm` and similarly in plethsym add a SEEALSO for frobenius. The problem with the name frobenius is that it is not at all descriptive (because there are other things that are named after Frobenius e.g. at one time the documentation had Frobenius omega automorphism, but I am more thinking the map that is more commonly called the Frobenius map from the ring of characters to the symmetric functions). Can I request that you use adams_operator or something like this instead?
• I don't want to undo if what you already tried, but in elementary.py I see:

(coeff if (sum(lam) - Integer(sum(lam) / n)) % 2 == 0 else -coeff)

is 1 if x%2==0 else -1 this faster than (-1)**x in this case? I tried experiments like timeit('[(-1)**v for v in range(1000)]') vs. timeit('[(1 if v%2==0 else -1) for v in range(1000)]') and the former was faster. Try:

(-1)**((sum(lam) - Integer(sum(lam) / n)) % 2)*coeff

or to avoid computing the sum twice

(-1)**((lambda v: (v-Integer(v/n))%2)(sum(lam)))*coeff

[darij]

Thanks for looking into that code! I'm fixing the issues now. But what exactly do you mean by whitespace issues? Do you have a handy regex for searching for them?

EDIT: adams_operation is now an alias for frobenius; good point! I don't want to remove frobenius, though, as it is a natural name from the Witt vector viewpoint. The other Frobenius map (the characteristic map) has a different domain, so no confusion can arise. The omega map I've never seen named after Frobenius outside of the code.

[zabrocki]

I always search for them by looking for <tab> and <space><newline>. On the editor I use it is '\t' and ' \r'

[tscrim]

It seems like there is something special happening for negative numbers / 1 / -1:

sage: %timeit (-1)**1000
1000000 loops, best of 3: 993 ns per loop
sage: %timeit (-1)**2000                    
100000 loops, best of 3: 968 ns per loop
sage: %timeit (-1)**5000
1000000 loops, best of 3: 924 ns per loop
sage: %timeit (-1)**10000
100000 loops, best of 3: 881 ns per loop

It probably is doing an if/then via modulus for "large" powers. So having it as (-1)**x is faster. Good caveat to know.

I agree that we should avoid doing the sum twice, but it's faster to store it as a variable instead of a lambda function:

sage: y = lambda a: 5
sage: %timeit y(2)
1000000 loops, best of 3: 770 ns per loop
sage: %timeit x = 5; x
1000000 loops, best of 3: 336 ns per loop

Any doc typos are my fault from copy/pasting.

Thanks for the comments Mike.

Best,
Travis

[darij]

Thanks!

About (-1)**a * x vs. x if a % 2 == 0 else -x: I've changed it to the former (= more intuitive) syntax now in the Verschiebung method. I was getting a speedup from the latter syntax in a different method (omega or antipode, I don't remember), which made me adapt it as a general tactic. I guess Python is smarter than that, though. Either way the time difference is small and tends to hide behind noise (my firefox is running), and I'm not sure whether it is due to the exponentiation itself or to the fact that the former syntax coerces (-1)**a into the parent of x and then does multiplication within that parent, while the latter only ever uses negation in the parent of x.

Uploading file now...

[darij]

Done. Someone (Mike? Travis?) should take a look at this as I've been making a lot of manual whitespace changes and who knows whether they're really all whitespace. ;)

patchbot:

apply trac_14775-qfolded.patch​ trac_14775-docstring_tweak-ts.patch​ trac_14775-response-to-mike-dg.patch​

[jdemeyer]

Please do not make whitespace changes to code you otherwise don't touch. It can only lead to merge conflicts and doesn't really benefit anyone. When you change code or add new code, it would be good not to have trailing whitespace. But that's no excuse for changing whitespace all over the place.

[darij]

OK, Jeroen, you tell me what files should be removed from the patch. No offense but I'm tired of following unwritten rules. Currently, every file changed by this patch is changed in a nontrivial way (not only whitespaces), although in three cases (jack.py, kfpoly.py, macdonald.py) it is all cosmetics (typos fixed in the doc). In all the other cases the changes are more substantial (e. g., wrong docstring rewritten). I have no idea what is the threshold for a change you consider beneficial.

[jdemeyer]

Replying to darij:

I have no idea what is the threshold for a change you consider beneficial.

The threshhold is easy: anything that is not purely a trailing-whitespace change. Fixing typos is good, rewriting docstrings is good, changing non-trailing whitespace (in a ​PEP-8 compliant way) is good.

I seem to recall that the git workflow will ignore trailing spaces anyway, so the "problem" will disappear anyway.

[darij]

Fine -- am I seeing it right that there is nothing to change then, because every file has got more substantial changes than just trailing whitespace?

[jdemeyer]

Replying to darij:

Fine -- am I seeing it right that there is nothing to change then, because every file has got more substantial changes than just trailing whitespace?

Well, the first file in trac_14775-response-to-mike-dg.patch​, sage/combinat/sf/classical.py, seems to have only trailing-whitespace changes. Moreover, it's not just a matter of "which file". Making a one-character change in a given file does not suddenly mean that you should remove all trailing whitespace in that file.

[darij]

OK, I can revert classical.py. For some reason I thought I changed it in the old patch, but I didn't.

About the rest: Well, sorry, but I'll need a more precise statement of what changes should be reverted if I'm to revert anything. What is your quantum -- if not a file, a class? a method? That said, I'm not convinced the theoretical possibility of conflicts in this particular case justifies causing Mike and me more trouble (Mike is apparently writing a followup patch to this, if I got his email right) and delaying this even further. I've taken notice of the general rule about whitespaces now, but apply it retroactively seems just as much a pain in the ass as what it is trying to prevent.

[jdemeyer]

Replying to darij:

What is your quantum -- if not a file, a class? a method?

A method at most (even less for "big" methods which I admit is not well-defined).

That said, I'm not convinced the theoretical possibility of conflicts in this particular case justifies causing Mike and me more trouble (Mike is apparently writing a followup patch to this, if I got his email right) and delaying this even further. I've taken notice of the general rule about whitespaces now, but apply it retroactively seems just as much a pain in the ass as what it is trying to prevent.

Fair enough, restoring positive review.

[darij]

Thank you!!

[nthiery]

Replying to jdemeyer:

Replying to darij:

What is your quantum -- if not a file, a class? a method?

A method at most (even less for "big" methods which I admit is not well-defined).

My rule of thumb is that, if I change a given line and see a trivial thing to fix in the couple neighbour lines, I go ahead, and otherwise leave it alone.

[jdemeyer]

Replying to nthiery:

My rule of thumb is that, if I change a given line and see a trivial thing to fix in the couple neighbour lines, I go ahead, and otherwise leave it alone.

Yes, that sounds right.

[nthiery]

EDIT: now applies correctly

[nthiery]

For the record: I removed to trivial whitespace fixes from trac_14775-response-to-mike-dg.patch which were already handled by #14866 and created a conflict. I allowed myself to leave the positive review.

[darij]

Applies correctly on top of #14866; thank you very much!

[tscrim]

Currently this causes a (very small) conflict with #14102 (which depends on #10963). Should we:

• revert the changes in this patch around where the conflict occurs (approx. line 826-830)?
• remove the changes in ns_macdonald.py to a ticket depending on #14102?
• rebase #14102?

[darij]

nthiery has just rebased #14102, hasn't he?

[tscrim]

Yep. Thanks Nicolas.

[zabrocki]

I added a number of doc changes consisting of mostly cleaning up references, a few missing colons, some extra imports caught by pyflakes, corrections of broken links, etc. Please check my changes again carefully.

[darij]

The changes are good except for one typo you can't help making. I have fixed the typo and added a couple more docstring changes. Once you've looked into them, this is positive_review, right?

patchbot:

apply trac_14775-qfolded.patch​ trac_14775-docstring_tweak-ts.patch​ trac_14775-response-to-mike-dg.patch​ trac_14775_more_review-mz.patch trac_14775-final-changes-dg.patch

[tscrim]

I'm good with the changes. If Mike is also happy with the final version of the patch, Darij, could you fold all of the patches together? Thanks.

[zabrocki]

You'd think that doing that twice that it was on purpose, but it isn't! Mea culpa!

I approve.

[darij]

Thanks again, everyone!

patchbot:

apply trac_14775-the_big_crunch.patch

[jdemeyer]

Sorry, but all changesets qfolded is not a good commit message, it doesn't describe what the patch does.

[darij]

qfold of all previous patches in this ticket

[darij]

Commit message fixed.