These programs all do the same thing, which is exit with a value of 42. In other words, the absolute minimum while still being able to demonstrate that they did, in fact, do something. Several of these programs are described in detail in other essays; they are included here for the sake of completeness.
If you wish to verify for yourself that these programs do, in fact, work, you can download the assembler source files and build them with nasm. Each program includes explicit build instructions at the top of the source file.
This is the final version of the program from the original essay. This is the smallest a Linux ELF executable can be.
This is the final version of the program from the second essay. This is the smallest a Linux ELF executable can be without violating the requirements described in the ELF specification.
This is the final version of the program from the third essay. This is the smallest Linux ELF executable I have been able to create while being fully standards-compliant and linking with libc. I do not know if a smaller executable is possible.
Occasionally people wonder if Linux's handling of 64-bit ELF files allows for a similar range of devious compression. In general, 64-bit ELF files are both larger and less forgiving of invalid values than their 32-bit counterparts. But that doesn't mean that nothing can be done. This program takes advantage of some tricky overlapping to get its size down below 100 bytes.
For the sake of completeness, here's a 64-bit executable that adheres to the requirements of the ELF specification. Frustratingly, I have been entirely unable to overlap the program segment header table at all with the ELF header, so the only creative space-saving in this program comes from storing the program instructions in the p_vaddr and p_paddr fields.
ELF is hardly the only executable file format that Linux kernels can support. Though it's uncommon now, at one time the native Linux executable format was aout files. The aout file format doesn't support dynamic linking, and in fact it is a very simple format. It requires only a simple 32-byte header, making it easy for it to be smaller than the smallest ELF executable. (Note: the last time I tested this — admittedly many years ago — the kernel would complain about aout binaries with a size that was not evenly divisible by 4K, but it would still allow them to run.)