Résumé : Our work focuses on the challenge of detecting outputs generated by Large Language Models (LLMs) to distinguish them from those generated by humans. This ability is of the utmost importance in numerous applications. However, the possibility of such discernment has been the subject of debate within the community. Therefore, a central question is whether we can detect AI-generated text and, if so, when. In this work, we provide evidence that it should almost always be possible to detect AI-generated text unless the distributions of human and machine-generated texts are exactly the same over the entire support. This observation follows from the standard results in information theory and relies on the fact that if the machine text becomes more human-like, we need more samples to detect it. We derive a precise sample complexity bound of AI-generated text detection, which tells how many samples are needed to detect AI-generated text. This gives rise to additional challenges of designing more complicated detectors that take in $n$ samples for detection (rather than just one), which is the scope of future research on this topic. Our empirical evaluations on various real and synthetic datasets support our claim about the existence of better detectors, demonstrating that AI-generated text detection should be achievable in the majority of scenarios. Our theory and results align with OpenAI's empirical findings, (in relation to sequence length), and we are the first to provide a solid theoretical justification for these outcomes.