This is a purely theoretical question. I've found some similar questions, but they're not what I'm asking.
Most importantly, I'm not asking whether anyone can find the hypothetical duplicate. I'm not asking about the probability of encountering a collision, or how long it would take. In short, for my purposes, pretend you're coming to this from a non-crypto math background, and consider all finite numbers to be small, and imagine that you're allowed to do exhaustive searches of any finite space.
For any given key, there is obviously a 1:1 mapping from plaintext to ciphertext.
Now, consider a specific fixed plaintext. There are 1<<128 possible keys. There are 1<<128 possible ciphertexts.
Either there's exactly one key that produces each ciphertext, or at least one ciphertext results from at least two keys, and at least one ciphertext results from zero keys.
If you imagine AES as simply selecting random permutations, this is the birthday problem, and it's effectively certain that there are duplicates -- at least two keys will produce the same ciphertext from your given plaintext, and at least one ciphertext will never occur from that plaintext.
But AES doesn't select random permutations. It selects pseudo-random permutations. The selection process can't select every possible permutation; it can only select some of them. And it is conceivable that the set of permutations it can select has such a trait.
It is trivial to devise a scheme which produces non-overlapping permutations, as long as the number of keys doesn't exceed the number of possible plaintexts. For instance, "treat key and plaintext as unsigned 128-bit values, add them, that's your ciphertext" would have this property.
I have no practical applications for this, but if you want an impractical application: If AES did have this property, then you could interchange the roles of key and plaintext. You could send people blocks that were AES encryptions of a known plaintext, and they could simply look up the key in their table of "which key produces each ciphertext from that fixed plaintext". (Sadly, that table appears to require more storage space than our universe has atoms, but practicality is not my strong suit.)
EDIT: I did find AES-128. Do there exist two different keys for a pair (text, encrypted text)?, but I think that answer contains a flaw, which is that it assumes that the permutations are random, and that the way they are generated isn't influencing the selection of permutations, for instance, making them less likely (or more likely!) to overlap. I'm questioning that underlying assumption.
Specifically, it's this bit here:
What if instead of uniform random πi we had πi=AESki for uniform random strings ki? If you could predict how that would affect the distribution nonnegligibly, you could distinguish AES from a uniform random permutation, violating the pseudorandom permutation family property that it is conjectured to exhibit, and there would be lots of cryptographers who would like to have a word with you.
(sorry for cut and paste formatting)
This isn't right, though. Think about block-cipher mode with a fixed key, and cycling through the (1<<128) possible plaintexts. You can't distinguish the output from a series of 128-bit random values in any way... But with an actual series of 128-bit random values, you'd virtually certainly get at least one duplicate by the time you did all the inputs, and with AES-128, you won't. But that's the only observable distinction, so far as I know. There's no ranges that are more or less likely, there's no connection from one to the next, and yet, you will somehow just magically never hit a duplicate value.
So we already know that AES-128 has, in one context, the weird property that a series of values it generates is indistinguishable from a random series of 128-bit values, with the sole exception of "but you never get a duplicate until you've hit everything". I'm wondering if it might have that property in a different direction also.
