I use Ubuntu 9.10 64bit and I can confirm this link are present with this release. To search for the package that contain a file I find apt-file handy: sudo apt-get install apt-file sudo apt-file update and then apt-file search libX11