Smallest possible universal combinator I am looking for the smallest possible universal combinator, measured by the number of abstractions and applications required to specify such a combinator in the lambda calculus. Examples of universal combinators include:


size 23: λf.f(fS(KKKI))K
size 18: λf.f(fS(KK))K
size 14: λf.fKSK
size 12: λf.fS(λxyz.x)
size 11: λf.fSK


where S = λxyz.xz(yz) of size 6 and K = λxy.x of size 2 are the combinators of the SK combinator calculus. The first 4 examples are described in this paper.

My questions are:


Are there any universal combinators that are smaller in size?
What is the smallest possible universal combinator?


EDIT: See also https://math.stackexchange.com/a/180263/76284, which has λazbc.bc(a(λy.c)) (which would be of size 8, matching the sum of sizes of the SK basis). Does anyone know how to express S and K from this combinator?
It should be noted that finding combinators with certain reduction properties is always difficult, and finding the smallest such combinator may easily be undecidable (for trivial reasons, as it may be undecidable to prove that a certain application of the combinator even halts).

There are several simple open questions of a similar flavor, e.g. problems #4, #6 and #10 from the TLCA list of open problems.

One thing to note is that your combinator certainly needs to have at least 2 bound variables, one of which is duplicated (as does any complete set of combinators) and one needs to be erased. This puts a lower bound of 4, I think (2 abstractions and 2 appearances of a variable), which is not so far from the upper bound of 11.

Edit: Noam's comments and reference push the lower bound to 5! I wouldn't be surprised if the proof also requires the extra variable to appear as well, which would push us to 6.