Can air bubbles sink at extreme depths? I was thinking earlier about air bubbles in water. if you had a bubble of air (say in a balloon) then as you take it down in water the bubble shrinks because of the pressure and because it is compressible. This means its density increases.
Water on the other hand being incompressible remains the same density at whatever depth you are at (I don't know if it is truly incompressible but I am assuming if it is at all compressible this is insignificant).
Does this mean that there is a depth at which an air bubble would be denser than the surrounding water and thus sink instead of float?
Would the gas at this density be doing things like turning into a liquid? Is the depth such that this is not even vaguely realistic? I feel like the situation is probably a lot more complicated than it is in my head which says that you would get air bubbles sinking at sufficient depth?
 A: Even ignoring that under high pressure the gas won't likely be a gas anymore, let's see what kind of pressure would be required.
Air is a mixture of N2 and O2 with molecular weights of 28 and 32 respectively.  There is more nitrogen than oxygen, so let's use 29 for the molecular weight for "air".  One mole of air therefore has a mass of 29 grams.  At 20°C and 1 atm pressure, 1 mole of ideal gas will occupy 24 l.  Our air will therefore have a density of 29g / 24l = 1.2 mg/ml, or 827 times less than water.  Therefore, at 827 atm pressure, the density of air will equal the density of water.
However, this is just blindly applying the ideal gas law.  Real gasses aren't ideal.  They go thru phase changes and deviate from the ideal gas law, particularly at high pressure.  To find out if you still have a gas bubble, look up to see what both nitrogen and oxygen do at 20°C and 827 atmospheres of pressure.  That's about the pressure at 5 miles down in the ocean.  Actually that pressure doesn't sound that high.  Both nitrogen and oxygen could well still be gasses at that pressure and 20°C, but I haven't looked it up.  Also, water isn't totally incompressible.  You should look up the density of water at that pressure and adjust the numbers a bit.
However, the reason we don't see bubbles of nitrogen and oxygen gas on the seafloor in deep trenches is because these gasses dissolve in water, more so with high pressure.
A: We need a phase diagram for the gas in the balloon. I found one for CO2

The pressure at the bottom of the ocean can be estimated as 1 atmosphere every ten meters depth. For 4000 meter that is 400 atmospheres.
Temperatures at the bottom  of the ocean are above icing, a few C, so from the diagram a balloon with CO2 released by a bathysphere at a suitable depth , would start turning  to liquid as the pressure equalizes with the water pressure from about 100 meters (above 10 atmospheres), for temperatures usual to the sea. 
Since CO2 is heavier than H2O I would expect it to sink to the bottom.
Edit after comments:
Better charts readable with accuracy can be found in this IPCC report: and the comment below is right that higher atmospheres are necessary for CO2 liquid at  around zero temperatures, over 200. In addition for sinking the density versus curvature curve in the same link has to be consulted where we see that the two phase region extends at these temperatures up to 900 atmospheres, so sinking will not take place before then.
A: The question is for an "air" bubble; basically 79, 20, 1 % N2, O2, Ar.  And we want to know if the bubble will sink.     But we don't have an "air" bubble; we have a balloon with air in it.
So at quite a modest depth, the air volume will be so small that the density of the balloon dominates, so it will then sink, since rubber or latex is denser than water by far.
So do you really want a balloon or an air bubble ??   For an air bubble to exist in water, the total pressure inside the bubble has to exceed the ambient water pressure, by 2t/r where t is the surface tension of water, and r is the bubble radius.   The deepest ocean is about 36,000 feet, and the pressure down there is about 1090 atmospheres (33 ft per atmosphere in salt water).
Since water is denser that 1090 times air at atmospheric pressure, the air density can never exceed the water density, so the bubble can never sink.   If the air liquefies or solidifies at 1090 atmospheres, and about a few deg. C, then we no longer have any air bubble to go anywhere.  So an air bubble can't sink in the ocean.
A: If you are hoping for a gas that can compress to exceed water density without itself condensing into a liquid, my guess is that the search will be difficult if not impossible. Uranium hexafluoride at 5 bar and $120^\circ C$ is a gas that is denser than liquid hydrogen for example but LH2 cannot exist in this condition. I would be interested to know which gas less dense than water can be compressed over the density of water without liquefying. Someone with more experience in chemistry should be able to prove why such a gas doesnt exist.
You will have to accept that the only way for a balloon to sink as it goes deeper is for the gas inside to liquify as it achieves depth/pressure, thereby shrinking the balloon and increasing its density over that of the water it is submerged in. The alternative is to go so deep that the water itself freezes and traps the balloon in place (but that violates the spirit of the question if you ask me, even more so than condensation of the gas!).
With water it is even more impossible to find such a gas for the air bubble (I am now venturing a little bit into chemistry). $H_2O$ is a very special molecule in that it has extremely high intermolecular interactions (Hydrogen bonds) for such low molar mass--basically it takes up very little space (very high density) despite its simplicity as a compound. When considering a balloon gas of similiar chemistry, a suitable candidate molecule is ammonia $NH_3$ which is gaseous in room conditions and relatively easy to condense by pressure, but in liquid form is still nowhere near as dense as water ($0.667x$ at $500 bar$) despite the similar molar mass.  
I tried sulphur hexafluoride $SF_6$, a gas famous for its high density--the phase diagram suggested that condensation could occur at $0^\circ C$, or $273K$ at around $15bar$. The difficulty is obtaining the density of liquid $SF_6$ at this temperature. My source suggested $1.98x$ relative density (relative to water) at $50^\circ C$ and $1.33x$ at $25^\circ C$. With the lack of data, a manual extrapolation would place liquid $SF_6$ at less dense than water if temperature was $0^\circ C$, i.e, the balloon would not sink. The source suggests however that given a $150m$ deep tank with water at least  $25^\circ C$ $SF_6$ will produce the phenomenon of a balloon sinking at that critical depth.
But I wasn't satisifed. There had to be a molecule that was gaseous as room conditions, liquified easily, and had molar mass higher than water. That molecule is 1,1,1,2-Tetrafluoroethane, a CFC gas--which I realised was similar to ammonia in that they are both refrigerant gases. Tetrafluoroethane doesnt have those hydrogen bonds, but because of the very electronegative fluorine atoms only on one side of the molecule, there are some very strong dipole interactions (easy to liquefy this gas). And of course, the high molar mass means the liquid form is likely to be denser than water. 1.295x density of water at just 3 bar, $0^\circ C$. At $25^\circ C$ the required pressure rises to 6.6bar, but relative density is still >1.2x.
So if you ever get your hands on a balloon full of nasty HFC-134a refrigerant, you don't have to dive deep to see something really cool, like a floating balloon suddenly collapsing at a critical depth and starting to sink. 
REFS
http://encyclopedia.airliquide.com/images_encyclopedie/VaporPressureGraph/Sulfur_hexafluoride_Vapor_Pressure.GIF
http://home.earthlink.net/~jimlux/hv/sf6.htm
http://en.wikipedia.org/wiki/1,1,1,2-Tetrafluoroethane_%28data_page%29
http://en.wikipedia.org/wiki/1,1,1,2-Tetrafluoroethane
http://www.peacesoftware.de/einigewerte/calc_r134a.php5
