Since the Tsars, night trains have tied the Russian lands together. Immigrants squat outside the Soviet baroque colonnades of Moscow's Kazan station. Swapping cigarettes and tips, these unemployed young men from Siberia and Central Asia tell me they are too poor to start families back home. Ulan is from Kyrgyzstan. He wears clothes of the worst imaginable quality. "My family taught me to speak Russian. It has always been like this. This is the centre, the hub." He will soon be joining the ranks of thousands of Muslim labourers who sweep the capital's streets and work on its building sites. 

On the clattering train to Kazan, the capital of the federal republic of Tatarstan, a bearded Islamist mistakes my Semitic features for an Arab face. He speaks earnestly, as all believers do. His hand never strays far from the Koran. Once the other passengers are asleep, he speaks of the future. "In Tatarstan, we are slowly undoing centuries of colonisation, building the mosques and spreading our networks. The time is coming when there will be too few Russians to control us. The demographic crisis is our great chance. Russia will collapse again, it has to." 

There are many new mosques in Kazan, linking the Tatars back to the Islamic world. Across the Russian republics, where people follow Islam, a steady revival is taking place. There were only 300 mosques in 1989. Today, there are 8,000. There are now more than 20 million Russian Muslims. But to say exactly how many is to enter into an often hysterical debate. Numbers as high as 26 million have been cited. Russian churches have shrilly sounded the alarm that Muslims may outnumber Christians by the end of the century. Some demographers even claim that more than one third of conscripts into the Russian armed forces will be Muslim by 2015. Demographics are notoriously unreliable and invisible. But changes are not. President Dmitry Medvedev has recently called for imams to care for Russian soldiers. 

But this data hides the fact that most Russians practise no religion and remain deeply Sovietised. Ivan, the owner of a Kazan pizza joint, tells me his family is typical . "I'm half Jewish, half Ukrainian. My wife is a bit German and the rest is Polish and Russian. My son's girlfriend is half Tadjik. Empire has brought the mixing of races through the centuries. Just look at our eyes, they are slightly Asian." There are two words for national belonging here: Russki meaning ethnic Russian, and Rossiyanin meaning inclusive of ethnicities, like British to English. In Tatarstan, the population is equally divided between Russians and Tatars, of whom one fifth are Christians. Coexistence is not easy. But in Kazan there is a vague Eurasianism. 

The North Caucasus is different. Across the region the slogan "Friendship and Brotherhood to the People of the Russian Federation" can be seen on billboards. But its omnipresence suggests things are rather different. Russian military expert Alexander Golts explains why: "The North Caucasus are the last provinces of a Russian Empire. They were drawn into Russia by Stalin despite profound cultural differences. The price that we have paid for retaining these territories is huge. In Chechnya, the price is the imperial vassal Ramzan Kadyrov and the barbaric security operations. The cost is the barbarisation of the federal state." The summer saw large-scale bombings and killings in the region.