"The Signals", a short story by Francis Cartier; first published in Analog Science Fiction -> Science Fact, July 1966; reprinted in the 1984 anthology From Mind to Mind: Tales of Communication from Analog (Stanley Schmidt, ed.), which was published both in digest format (the same as Analog) and also in hardcover. The anthology From Mind to Mind can be "borrowed" from the Internet Archive (free but registration required). The July 1966 Analog with "The Signals" is available in the Luminist archive.
"The Signals" was the first in Cartier's Signals series of short stories in Analog; the others are "The Frequency of the Signals" (October 1986), "The Day the Signals Started" (March 1991), and "The Day the Signal Stopped" (January 1993). The whole series is about various failed attempts at interstellar communication. The viewpoint alternates between Earthians (SETI scientists and others) and various aliens who are trying to signal us.
Aliens sending a random signal:
"We are sending," he said in a tone usually reserved only for children, "the most unnatural and the most fundamental concept in mathematics, the one concept from which all mathematics arises, and upon which all mathematical order is ultimately based."
"Ah!" said Aom, looking pleased with himself, "Zero!"
Eeal had a momentary feeling of revulsion at such senility, but Aom was a gentle being and often provided the only calm voice in a stormy argument. With some effort, Eeal kept his patience.
"No, Aom," he said smoothly. "How could we possibly send such a message? No. As you know, all natural signals, having natural causes, show patterns when properly analyzed. We are sending an absolutely perfect random series."
The story ends with aliens trying to make telepathic contact with the SETI project directed by Dr. Ward:
"What was it, Obie?" he asked without looking away from the recorder.
"I'm not sure. I don't know. I just suddenly heard—Or, that is—It was the beginning of a message."
"In English?" Ward's shoulder muscles tightened as he waited for the reply.
"Yes," Obie said quickly. Thee was a pause. Then, quietly and thoughtfully, "No." Another pause. "Yes. It was." O'Brien dropped heavily into his swivel chair. "Let me think. I was sitting here at my monitor. I had just adjusted the frequency according to the schedule. It's still set the same way. Something started coming through. There was the word earth," and then, his face contorted with concentration, "I think."
Ward's shoulders slumped as he prepared to play the tape back. There would be nothing on it.
Two hours later, after several replayings, Ward put the computer back on stand-by mode, returned the recorder to antenna duty, and wearily eased himself into his chair. There was nothing on the tape. O'Brien, like the four others before him—or was it five?—had obviously fallen victim to the boredom and the unrelenting pressure of concentrated waiting. It was the same old pattern: late in the shift when they were tired and their resistance was low, and always after several years of listening, straining, hoping, trying, trying, trying. It was the young ones who were most susceptible, and usually the girls. But Obie was a sensitive, emotional type. Well, he'd have to let Obie go, too.
[. . .]
The strength of 778's thought was so strong that 842 turned to look across the room at him. "I know," he thought to 778, "it's frustrating, isn't it. But there just has to be a way to get through, perhaps even to Ward himself. If only we knew what all that machinery of his is for—"
