Are poly1305 authenticators distinguishable from random data? Assume Alice authenticates a message $M$ with nonce $N$ and secret key $K$, creating authenticator $A$. She then sends $A$ across the network.

The Poly1305 paper does not seem to specify whether it is possible for an adversary, whom has seen $A$, to determine whether $A$ is just random bytes or has characteristics of an output from poly1305. 

For someone interested in deniability, this is an important distinction. Are poly1305 authenticators distinguishable from random data?
No, they are not distinguishable from random.

The Poly1305-AES authenticator is defined as:

$$
(((c_1 r^q + c_2 r^{q−1} + ... + c_q r^1 ) \bmod {(2^{130} - 5)}) + \operatorname{AES}_k (N)) \bmod 2^{128}
$$

Since it is the sum of an AES output and some other number modulo $2^{128}$, it is PRF if:


the AES output is PRF and
the two numbers are independent.


AES output looks like PRF as long as you see less than ~$2^{64}$ of them and $k$ and $r$ are required to be independent (since they are chosen from a uniform distribution), so the authenticators are indistinguishable from random at least as long as you see significantly fewer than $2^{64}$ of them.