It depends how you define Linux. If you ask for current operating systems then we are talking about way above 100MByte, better 1000MByte of memory.
If we are talking about "Linux from Scratch" then we are also talking about how much pain you are willing to suffer. In the mid-1990 I build a Linux system by compiling every binary myself and made it run on a 386sx16, 1,5MByte of memory. While it had a 40MByte harddrive it was mostly empty. I compiled my own Kernel 1.0.9, my own libc5, my own base tools, SVGAlib. That system was somewhat useable for using textmode and SVGAlib applications. Increasing the memory to 2MByte did help a lot. And believe me, the system was extremely bare. Today all components need at least twice the memory but then there is also ulibc instead of libc and busybox.
At 8MByte of memory I can create a very basic system today from scratch. At 512MByte of memory you might have a somewhat modern looking but slow desktop system.