It's done on-device to handle the problem of linking. All calls from the app into framework have to be linked when you do AOT, and Google can't do that without having device images of every android device and compiling on-demand for whatever device is requesting the install.

And then you'd still have to fall back to on-device compilation if Play Store doesn't know what the device is anyway (aka, all custom ROMs), or when you take an OTA (otherwise you'd need to re-download all installed apps for the new OTA image).

Plus, the dex bytecode is considerably smaller than the AOT result, so wire transmission costs are cheaper doing on-device compilation - call it a form of compression.

The binaries produced from the AOT process are too large to download over the network for typical users and data plans.

Yet Apple and Microsoft managed to do it.

In fairness, they managed to do it only for the highest of high end users. Apple institutionally doesn't care about anyone in places like China, India or Africa where data is expensive. That's why Android completely dominates the global smartphone market share.

I guess nothing would stop the Play Store from AOT compiling binaries just for users with fast connections though.

Windows Phones were widely available in India, before everything kind of felt apart, though.

Microsoft ships .NET bytecode (so basically the same thing Android does) and Apple doesn't care about the low end.

No it doesn't.

WP 8 and 8.1 use MDIL, Machine Dependent Intermediate Language, basically machine code with jump targets kept as symbolic links, replaced at installation time.

WP 10 uses .NET Native.

I can gladly point out the respective Microsoft documentation, BUILD and Channel 9 presentations.