A long great ethnic terror in the Volga region

Introduction

In order to understand the Great Terror in a wider perspective, and to situate ethnical groups within its logic, it is useful to concentrate on its "predecessors", i.e. systematic attacks against ethnicity in previous years, and to widen its geography to regions far away from the Union"s borders. From this point of view, the Volga region is in itself an interesting as well as a fruitful field for historic analysis. Moreover, since its integration into the Russian space 1 , it has been a complicated region to rule, where regular protests against Moscow took place2 .

The Volga region is a mosaic of nationalities. But, unlike Caucasus, ethnic groups are strong and numerous there, while they represent two sets of linguistic, historic and religious traditions. The first, historically an important playerin Russia"s history, is the Turkic family. The ethnical groups whose origins are connected with the Mongol occupation of Russia and the political power following its collapse, are very close to one another: while Tatars were at the core of the last Mongol state before its incorporation into Muscovite Russia, and Bashkirs were nomadic tribes difficult to control, they both spoke very close, mutually understandable languages and had a Moslem tradition. Tatars had a ruling tradition they had maintained after Russian occupation, which relied very much on the system set by Kazan Khanate and its civil servants; Kazan was a local metropolis, with a complex social structure and political life. On the contrary, the ethnical groups of the second set were more complicated and politically much weaker: there were several of them, mostly peasants in Russian dominated regions, without any ruling experience, speaking different and mutually incomprehensible languages belonging to the Finno-Ugric language group, living in more or less compact areas, more or less Christianised on the substrate of animistic world views. They were the Mordvins 3 , the Maris 4 , the Udmurts 5 , and the Komi 6 .Therehad never been any unity or connection within these communities. None of them had ever ruled a state they had always been submitted to an ethnically different group. There were no cities in their territories, and political organisationwas very weak 7 . They have thus never represented any challenging political danger for central power: even when they participated in the different historic revolts, they were never the initiators. It is thus interesting to follow their fate in Russian Stalinist repressions.

The Soviet state and ethnicity in the Volgaarea in the 1920-1930s

One of the peculiar and unexpected ideological standpoints on which the Soviet state was actually built is the structural power of ethnicity [START_REF] Slezkine | The USSR as a communal appartment, or How a Socialist State promoted Ethnic Particularism[END_REF]. The stress on ethnicity was not part of the Marxist dogma; ethnicity was viewed by strict Marxists as part of the so-called superstructure that was not at the core of the understanding of society. But strict Marxists had not a multicultural empire to manage, as had the Bolsheviks after 1917: "Nations might not be helpful and they might not last, but they were here and they were real" (Slezkine 1994: 415). They had to build support for their rule in complicated conditions and sought the support of the weakest of ethnic groups, which were not previously politicised 8 . The weight of ethnicity in the building of the Soviet State must not be underestimated. Several authors have emphasised that the Soviet Union was a triumph for the principle of ethnicity. This understanding led to the establishing of a territorial network of ethnical groups who were "given" so-called autonomy at different levels.

Among them, the Volga peoples become nations. They are allowed to develop their culture within the Soviet framework, and all of them (except the Mordvinians) were allocated a territory 9 in which to develop their own cultural and political goals. A material contribution towards the achievement of this framework was the activity of the autochthonous peoples" young and numerally smallintelligentsia, whose aims were more cultural than political. They were given carte blanche to develop their people"s cultural building and required in return loyalty that was freely and gratefully given. At this stage, indeed, what the Bolshevik offered corresponded to the aims of the local intelligentsia. They came from a total absence of 5 Formerly called Votyaks, they livein a compact area. For centuries, the Southern groupsof Udmurts were incorporated in the Kazan Khanate while the Northern part was encompassed in the Russian Vyatka State. This has left traces on their respective cultures. On their territory, Russians developed since the 17th century metal and later weapon industries, while in the last decades oil has been found. 6 Formerly called Zyrians and Permiak. The two Komi groups are separated by forest areas. The group, the Permiaks, were since Russian conquest under the rule of the Stroganov family. In the north, the Zyrians occupy a huge taiga area. They were evangelised in the 14 th century and were thus better integrated than the others into the Russian world (cf. Toulouze 2010a; 2010b). 7 Actually I have left apart another Volga ethnic group, the Chuvash, which presents hybrid features. While these descendants of the Volga Bulgars speak a Turkic language (but quite different from Tatar and not automatically understandable), the rest of their history is akin to the Finno-Ugric groups. As I have not studied this group, I will not dwell on its history. 8 Just after the revolution, some of the most ethnically aware of Russia"s nationalities, the Western groups, either formed their own states (Finland, the Baltics, the Poles), or remained within the borders of the Soviet State, but with difficult relations (the Ukrainians). The Tatars were, as I mentioned, highly politicised, and they were uncomfortable allies for the Bolshevik. 9 Mari and Udmurt Autonomous oblast" were created in November 1920, the Komi A.O. in August 1921. recognition and were provided the means to build a cultural life, to develop school in their languages, to express themselves and to gain for their communities a dignity those never had.

Still, both in Udmurtia and in the Mari region (the two areas I am going to focus on), the intellectuals that enthusiastically worked with the Bolshevik, were usually members of the party, while the CommunistParty was smart enough to integrate them at postsof responsibility10 . Some joined the party later. Others never did, but this did not lessen their enthusiasm. In this remarkable period, which starts as soon as the Civil War is over (or even before), the promotion of the natives was one of the party"s concerns, which is well expressed with the policy of indigenisation, коренизация, whose aim was of developing vernacular language"s knowledge by the non-native, aliasmainly Russian population and to ensure the recruiting of native managers and executive, for "nationals" were weakly represented at leading positions (Egorov 1929: 8, Kulturnoe 1970: 149, Sidtikova 1990: 38). Moreover, in some conflicts that emerged in the 1920s, Moscow regularly supported the local national leaders against the Russian-minded party or state officials11 . It still followed Lenin"s approach, who was definitely hostile to Russian nationalism (Slezkine 1994: 414) and sympathised with mere cultural building, according to the best missionary traditions12 .

While following these regions" political developments in the 1920s, it is clear that two tendencies co-existed in the party"s leadership: one dominates at the moment and inspires the party"s policy towards the Volga nationalities and is quite friendly and supportive of the intellectuals" involvement in promoting their culture within the socialist system.The other is at the beginning of the 1920 a minority, strongly Russian-minded and hostile to nationalities" promotion; according to their understanding, these policies divert the party from the main goals, the building of a proletarian nationless society. In the party"s discourse, all over two decades, these tendencies appear in the opposition against two extremes that are considered as menaces against the party"s righteous policy. One is the "great-power chauvinism"13 , the other, the "local nationalism14 ". While at the beginning, the first was considered as the main peril (Pesikina 1956: 96), the second becomes, in the 1930s, the most subtle and dangerous enemy of the Soviet power (Lallukka 1990: 65). This Russian-friendlytendency, which is contained by Moscow policy at the beginning of the 1920s, is very much present, especially in Udmurtia (with the strong proletarian Izhevsk" factory party organisation). The newspapers report many protests within the party against indigenisation, and numerous refusals to learn Udmurt; moreover, as soon as 1926, the leader of the Udmurt intelligentsia, who is also the leader of the newly created Udmurt writers" Union, is compelled to resign, because of a row with the party leadership. These are marginal, but clear signs that the official place given to ethnicity, and especially non-Russian ethnicity, is not willingly accepted by many Communists.

During the second half of the 1920s, this Russian-minded wing of the party becomes the leading one. The rhetoric of the two dangers does not disappear immediately, but it is used in order to show the enemy"s cunningness: local nationalists hide themselves speaking deceitfully against Great-Russian chauvinism (Dimanshteyn 1937: 7).

On the general level, collectivisation in 1928 is a brutal aggression against the ethnic groups that are mainly rural (as the Volga Finno-Ugrians), with the elimination of the rural society more active members, who are repressed as kulaks; but while de facto it endangers their vital strength, it does not target directly ethnic groups as such. Still, the impact is huge and may be assimilated to terror. In Udmurtia, for example, while according to the statistics, the wealthy peasants represented 2,3% of the rural population, more than 30% was eliminated for being kulaks (Nikitina 1998: 164). Another field in which repressions started with collectivisation is the spiritual domain. Until the end of the 1920s animism was tolerated partly because the Russian Orthodox Churchhad fought against it. With collectivisation everythingchanges. Among other thingsanimistic rituals are prohibited as something that wastes state commodities (e.g. animal sacrifices. This aspect of collectivisation, undoubtedly, may be assimilated to ethnic repression (Nikitina 1998: 130-131).

Attacks explicitly against ethnicity are to be noticed in the last years of the 1920s and the very beginning of the 1930s, before they transform into a calculated enterprise of national intelligentsia"s elimination. We shall follow now, after these first contextualising chapters, the forms of this war against the Volga nationalities on the example of the Finno-Ugrians.

I add a last contextualising comment about the notion of "Finno-Ugric". It is clearly a linguistic notion: the languages spoken by these peoples are of the same remote origin and connect them to the westernmost languages of the group -Estonian, Finnish, and Hungarian. Language, for the three state-building communities, is the leading identity factor. Since the first decades of the 19 th century, Finnish and Hungarian scholars have been looking for language kin in Eastern Russia and Siberia. While being situated far from Russia"s borders, the Volga people speaking a Finno-Ugric language were intellectually and emotionally connected with these countries, whose political sympathies were nevertheless not with the USSR. While the intellectuals of those minorities in Russia were sincerely devoted to the Bolshevik cause and looked towards Hungary or Finland, not because of their present politics, but because of their history and patrimony, trying to develop meaningful links and relations. Some examples: the Komi writer and linguist VasiliyLytkin (who wrote under the Komi name of Illya Vas") received a scholarship in 1926-27 to study in Helsinki and Budapest (Turkin 1995: 210-212;Turkin 1997: 22-25); KuzebayGerd 15 , who, besides being a writer, was also a student in Moscow, was able to get in touch with Finnish scholar Yrjö Wichmann, who had visited Udmurtia at the beginning of the 20 th century and who had collected oral poetry. Gerd was keen on returning the treasures of oral culture Finnish scholars had gathered from his people. Hewished to dialogue with his Finnish colleague, publishing an article in Finland through the Finnish embassy [START_REF] Haltsonen | К вопросу об изучении творчества К[END_REF]: 359, Kuznetsov 1994: 36, 82-89). Moreover, Finland was in some sensea model for Udmurt intellectuals: the discovery of a collection of Finnish poems translated into Russian showed Gerd the way he had to follow in order to develop Udmurt modern culture (Shklyaev1982:141). In his motives, there was nothing political, nothing threatening towards the policy of Soviet Russia. But it will be interpreted otherwise…

Finno-Ugric ethnicity as a danger

At the beginning of the 1930s, history and ethnography are thoroughly reviewed by the party, which decided that "bourgeois" tendencies had to be eradicated. Discourse about national issues apparently has not changed: local nationalism and "great power chauvinism" are still in focus. But great-power is no longer Russian: in a programmatic 1931 article, Matorinpresents as "great power chauvinism" what he defines as Ukranian ethnographers protecting Ukrainian kulaks against Russian proletarians (1931: 25-27). Another category emerges, " nationalchauvinism ": the peoples that are "national-chauvinistic" are the Fennic peoples 16 , supported by Finland, whose aim, allegedly, is to conquer Karelia and to create a "Great Finland " up to the Urals (31). This is a very important theme that appears it publicly for the first time.

While intellectuals, mainly Komi and Udmurt, tried to develop relations with the Western Finno-Ugrians, for the sake of scientific cooperation or to develop knowledge of their own culture, other scholars attempt, in the 1920s, to develop Finno-Ugric studies within the Soviet Union. They are aware that nothing exists in Russia, while research is quite advanced in Hungary, Finland and Estonia (LOIKFUN 1929: 3). For this goal, they create in Leningrad in November 1925 a Society of Researchers of Finno-Ugric Cultures (LOIKFUN 17 ) and try to coordinate the scholarly activities in the field 18 .

The most active scholars in Russia in the Finno-Ugric field, who are also involved in LOIKFUN, are Mordvinians, like Markelov 19 , and Komi, like Nalimov 20 . It is not surprising: both Mordvinians and Komi had been interated into the Russian world long before the other Central Russia communities, which had long been encompassed into Kazan Khanate, and thus 16 The Fennic peoples are communities speaking closely related languages in a continuum between the Curland coast (Livonians), Estonia, Finland and Karelia. In Russia, the Fennic communities are mostly (with the exception of Karelians, smaller communities: Votes, Ingrians, Ingria Finns, and Vepsian. 17 In Russian:ЛенинградскоеОбществоисследотелейкультурыфинно-угорскихнародов 18 The leader is Vyacheslav Egorov, a senior researcher whose course about History of Fennic peoples had just been suppressed at Leningrad"s University; he will not be allowed to pursue his research after 1929 (http://www.ethnology.ru/biobib/Result.php?fnc=459). 19 Mikhail TimofeevichMarkelov (1899-1937); for more details, see Churakov 2008. 20 VasiliyPetrovichNalimov (1873-1938), komi ethnographer. kept at distance from Russian influence. In the 1920s, Udmurts 21 and Mari 22 start to develop scholarly research: they cannot ignore Finno-Ugristics, for the discipline has collected huge amounts of precious materials. The creation of LOIKFUN allows older and newer generations to conceive a development plan for Finno-Ugristics within Soviet Russia. LOIKFUN published at least one collection of articles, in 1929, in which scholars from the different areas presented their works indifferent fields (for example, Kuzebay Gerd wrote there the first article, about contemporary Udmurt literature, cf. Toulouze 1996). LOIKFUN"s idea was one that would be realised later post-War Soviet Union: to organise regular congresses (LOIKFUN 1929a: 1) that would coordinate Soviet finno-ugristics, associating several local and cultural organisations (Kuznecov 1994: 300). The first congress was to take place in Leningrad in 1931. The preliminary text contained nothing provocative, it emphasised the study of Soviet realities as shows the theme proposed: "Report and needs of socialism construction by Russia"s Finno-Ugric peoples" (Loikfun 1929:2). No hint is made of any foreign scholar"s possible participation. The project is accepted by the Udmurt party in 1929 (Kuznecov 1994: 430-431). This is the last spark of hope.

In 1931everything changes, as announced by Matorin"s article in Sovetskaya Etnografiya. LOIKFUN is severely criticised for its "bourgeois" tendencies and its board is renewed (p.156). The union"s orientations lose independence and are just harmonised with the allover goals of Soviet organisations. Attacks against Finland are multiplied. One goal is "to fight against Finland"s fascist territorial ambitions"… (Kulikov 1997: 108). In the same issue of journal, the new chairman, M. Pal"vadre claims that "the aim of Finnish ethnography is to create the scientific preconditions for/implementing/the idea of Great Finland" (Pal"vadre 1931: 41). These attacks against Finland are soon completed by attacks against "Great Estonia", presented as a parallel to "Great Finland" (Kulikov 1997:109). The foreign dimension of Finno-Ugristics is explicitely formulated. At he same time, while political relations between the two countries are not the best, diplomatic relations stabilise a status quo: in 1932, a non-aggression pact was signed between the two countries. But what we are interested in, in the Volga is not foreign policy or diplomacy. It is instrumentalisation. Actually, the Finnish situation 23 is interpreted according to the principle that led Soviet 21 Grigoriy Vereshchagin was the first Udmurt ethnographer and writer; but he was quite isolated, and no other Udmurt acquired, before 1917, scientific reputation. 22 Mari intellectuals before the Revolution dedicated their efforts to education; the first Mari to become a recognised scholar is Valerian Vasilev (see later). 23 Let us addsome background information.Both Finland and Estonia are successor states and former parts of imperial Russia. Both states are anti-communist, hence anti-Soviet in their own political orientations, and Communist parties are marginalised or excluded from social life. The Soviet Union, either as a proletarian state and the coloniser, could not attract much sympathy from these states. On the other hand, in the national awareness that leads to independence ambitions, the language element is crucial: both Finnish and Estonian identitys are language-centred. And language is also the core of Finno-Ugric research. In the new states, some part of public opinion wants to develop particular links towards the other analogous countriesnewly independent, with strong patriotic feelings. In the three Finno-Ugric nations, motivated societies form the socalled Finno-Ugric movement, which is rooted in society and not only in academic circles: hõimuliikumine, heimotyö, rokonnépek mozgalma. The focus of these civil society elements is not the Soviet Union"s Finno-Ugric part. They are keen on developing relations among themselves, and as the Soviet Union is a closed country, they leave it apart of their activities. But within this movement, especially in Finland, there are more political wings. Triggered by historic Karelia"s position, and seing in Karelia the actual roots of the Finns, this extreme groups of ethnography: the political dimension and even instrumentalisation of science to State superior interests (Toulouze 2006: 35): the main scholarly organisations -SKS ans SUSare considered as fascist organisations. Still, the most interesting point of view expressed in these surrealistic articles is that Soviet science is not strong enough to confront its Finnish and Estonian counterparts. Is it an appeal to security services to take in charge the problem scientists could not deal with? Is it a preparation to what is to follow?

What is happening at the beginning of the 1930s is still not terror, but it is the beginning of the path leading to it.

The first manifestations of national repression

While the overall athmosphere was becoming tenser and tenser, in the national regions authorities turned explicitely against the intellectuals of the eponymous Finno-Ugric population. The first example ever of an operation against Finno-Ugric intelligentisa as such, with charges of nationalism and worse, takes place in the Mari region.

We shall now focus on this first faked process, which is interesting for several reasons. It is the first example of something that would become, in the following years, a most commun experience. Moreover, is seems to be a rehearsal for a much wider operation two years later: all the mechanisms have already been identified and implemented.

At the end of January 1931, six Mari intellectuals are arrested 24 . They are not members of the party, they all belong to the older generation and are accused of nationalism. Moreover, they are charged with "having organised a counter-revolutionary group, helped by Finnish secret services" (Tragediya 1996: 26). These people are among the most respected activists of Mari autonomy and Mari culture. The first to be arrested is the director of the regional museum, Timofey Evsev"ev, who recognises only that he had contacts with Finnish scholars (Kulikov 1997: 111). The elder of them, Valerian Vasilyev (called Üpö-Mariy, the Mari from Ufa), a teacher in Kazan university, is arrested some days later, as well as Leonid Mendiyarov (who worked at the Museum in Kozmodemyansk), A. Sayn (who was married to an Estonian) and some others (Tragediya 1996: 111).

The arrested men are examined and they are asked to reveal their opinions of the situation in the Mari oblast and about their connections with Finland. They are interrogated for two weeks, both in Yoshkar Ola and in Nizhniy Novgorod (Kulikov 1997: 111-113). They are finally accused of wanting, with their group "1. to separate Mari autonomous oblast" from the Soviet Union and 2. To gather intelligence for Finland" (Tragediya 1996: 113), and other charges.

people, who are not the most influential ones in societs, may exoress some ultra nationalistic positions that may provoke the Soviets" concerns. 24 Actually at the same time, a smalleroperationisledagainstsome Hill Mari "nationalist" group. But we do not know its links with Mari intelligentsia (Tragediya 1996: 27).

In december, the file is examined in Moscow and the charges fizzle out. Moscow refuses the accusation of the Mari being spies, and the Mari intellectuals are "only" exiled for three years for anti-Soviet activities (Tragediya 1996: 115).This ending, as well as the knowledge we have of the future, is probably why we interpret this episode as a rehearsal of what follows. This is the first example we have of clear criminalisation of being a national intellectual in a Finno-Ugric region. The accused Maris are all highly respected intellectuals, whose merits are directly connected with Mari nation-building. They are all involved in cultural "construction". Moreover, their loyalty towards the Soviet power, their sincere gratefulness cannot be doubted.

The first great process against Finno-Ugric intellectuals: the SOFIN

In the 1920s, the Udmurt leadership, as mentioned above, was reluctant to implement the pro-Udmurt policy promoted by Moscowthe party was dominated by Izhevsk plant communists, a dominantly Russian proletarian organisation. The position of the Udmurt leadership had not changed, but Moscow had now chosen more Russian-oriented policy. But there were tensions within the oblast. Can they be explained by this new support local authorities received from the centre? Certainly, positions that were just hinted at in the previous decade, are now explicitely asserted. The party leadership can express their dissatisfaction against intellectuals who felt involved in the Udmurt cause. Tensions accumulated around the poet number one, Kuzebay Gerd, who became the focus of harsher and harsher attacks and finally the victim of the first big process announcing wider and more systematic terror. The SOFIN affair is often called also the Gerd Affair (Kulikov 1997: 9).

Who is Kuzebay Gerd? Kuz"ma Pavlovich Chaynikov (1896[START_REF] Dimanshteyn ; Диманштейн | The Bolshevik resistance to nationalism[END_REF] was trained as a school teacher and participated enthusiastically in the revolutionary events. He was extremely active: he contributed to the establishment of Udmurt borders, wrote in the press articles and poems, played his plays in the countryside, lead an orphanage, was in charge of the party"s paper "Gudyri". After this extraordinary period, he studied poetry in Moscow with Valeri Bryusov and came back in 1925 to fulfil several tasks in Udmurtia: director of the museum, leader of the writer"s union. After some tensions he went back to Moscow in order to prepare two doctoral dissertations (in ethnography and folklore). He was called back in 1931 and, before he was arrested and tried, he was a university teacher. In those years, he published three collections of poems and several other works (textbooks, one short story, plays, collections of songs and folklore).

The crescendo against Gerd

The first sign of serious disapproval of Gerd was given as soon as 1926 at a teachers" meeting, through a row with the party"s secretary, who accuses Gerd, the chairman of the Writers" Union, of having bourgeois attitudes 25 . Certainly the poet"s open, extrovert personality, his charm and charisma, may have provoked personal jealousy and enmity all his life long. After this row, the party dismissed him from his positions at the editing board of the literary journal Kenesh, as head of the Writer"s Union and of the Udmurt Museum (Emelyanov 1988: 182-183). Later, he went to Moscow, where he spent some studious years in relative quiet and published in Kazan (not in Izhevsk…), his second collection of poems, whose reception was not very enthusiastic (Shklyaev 1988: 9;Ermakov 1988: 231) But some of his fellow students denounced him to the Udmurt Communist Party and he was called back without completinghis dissertations (Ermakov 1998: 14;Ermakov 1994: 36-37). I have not found any reasonfor this hostile attitude against a personality that was so appreciated by many. Two main hypothesesmay be brought forth: envy may be the first, i.e. personal reasons. The other may seem paranoiac. But if Gerd had already been chosen as the culprit to eliminate, the letter may have been inspired by local authorities to students willing to please. But these are only conjectures.

While going back home, Gerd is more and more targeted both in public speeches by party officials and in the press, and accusedof committing more and more political errors. After a public letter in 1931 by Udmurt Bolshevik Nagovitsyn, which is quite critical of Gerd"s political positions (Shumilov 1998: 217), in 1932, party secretary Elts"ov in a speech expresses the official position: "the mouthpiece for national bourgeoisie in literature is a wellknown poet, Gerd. Gerdism highly praises all our enemies, what remains of the kulak class, which we have eliminated, opposes all our initiatives, socialist construction (…) In our press, this kulak fights against Russian, against Russian workers and he calls backward Udmurts not to learn Russian" (Kulikov 1995: 75-76). This is a clear sign. Articles against Gerd, often signed by several persons, by colleague writers, becomemore and more frequent [START_REF] Kuznetsov | Кузнецов, Николай Спиридонович. Из мрака[END_REF]: 150, Shklyaev 1990: 30).

Hisrecent works are attacked. While clearly Gerd"s wish not to provoke leads him to more and more conventional workshis third 26 and last collection of poems, Grades 27 (1931) is not as original as the previous, both in form and in contents; while he sings the successes of the new life, his detractors find in his works negative metaphors against the party"s policies. For example in the poem "Storm in the village", an obsessive work with short verses, he is accused of slandering collectivisation (Shklyaev 1979: 79-80). But that"s not all. All his poems are analysed from the point of view of the party"s policy and dogma, even those that were written before 1917: he is accused ofidealising the past, praising the rich, exalting solitude and individualism, being melancholic, writing against the Russians [START_REF] Shklyaev | Шкляев, Александр Григорьевич[END_REF]1990). 25 According to Ermakov, Baryshnikovsaid, when Gerd criticised the educationauthorities:" Gerd"sbehaviourisintolerable, heopenly expresses contempt and disrespecttowards the Education Office civil servants (…). Gerd has not changedhisscornful attitude towards the Udmurts " (Ermakov 1988: 36). Gerd left the congressafterthisattack. 26 The two first are The citharist (in Udm:Крезьчи), Izhevsk 1922, and the second " The land in flower" (in Udm. Сяськаяськисьмузъем), Kazan 1927. 27 In Udm.:Лѐгетъѐс.

Arrests

In 1932 the pressure is such that it is almost a relief to be summoned by the NKVD to Nizhni Novgorod (Kuznetsov 1994: 48). OnFebruary 18,Gerd is asked to remain at the hotel and to write down all about himself. He is being interrogated for the next two months (Kuvshinova 1998: 68-69). After 1994, these documents have been found in KGB archives. As in other regions, a former Udmurt KGB official, Nikolay SpiridonovichKuznetsov published a book in 1994 informing public opinion about what has been forgotten and tabooed. The documents do not reveal under what pressure they have been written. By what I know of their contents, I do not doubt that as far as the Gorki texts are concerned, they reflect Gerd"s thinking. Gerd, who had been extremely wounded by the attacks against him, who not understand what was happening, tried to get things clear for himself. His notes are extremely logical. He does not neglect self-criticismbut this is praxis of the periodat the same time he insists on his will to act and to be useful (Kuznetsov 1994: 16;309). In the first stage of the procedure, probably he hopes that by an honest account of his thoughts he should be able to convince the prosecutors of his good faith. Now we understand that this first stage is probably meant to obtain materials that will be anywayturned against their author. Gerd is allowed to go back home, but as soon as May 13 th , he is arrested as well as some other Udmurt intellectuals. Gerd will spend one year and seven months in an isolation cell in Nizhni Novgorod (Gerd 1998: 34;Kuznetsov 1994: 48). Later, other Finno-Ugric intellectuals are arrested as well.

If not all intellectuals are arrested, many are terrorised. Poetess and physician AkulinaVekshina, Ashalchi Oki, had stopped writing earlier, when she understood that it wasn"t possible anymore to be honest in one"s writings. But in 1933 she is interrogated (Kuznetsov 1993: 61). Shedisappears as a poet yet being able to go on living as a physician. But she is clearly traumatised, as she writes in the 1956 to Kralina28 : "Who doeswrite to a dead person? The Ashalchi Oki whom you address has been buried long ago. A quarter of century has passed since I wrote and I have forgotteneverything. Anyhow, as long as I remember, I did not write anything since 1931. I have forgotten. I don"t remember a single poem, or story. After a psychological trauma, I destroyed all the Udmurt literature that I had in my library" (Kralina 1990: 25).

The SOFIN

The process starts in 1933 and finishes in 1934.

The files of this process cover thousands of pages that have not been opened to researchers, except some scholars in Udmurtia, like former KGB official Kuznetsov. The examination for Gerd is long and extremely detailed. He is even brought to Lyubyanka, where according to secondary information, he fell apart (Kuvshinova 1998: 70;Verner 1998: 227). There are several charges against the accused: ideological charges, reprehensible acts, intentions.

The ideological chargesrested upon ambiguous elements, which, speciously put together, create the framework: a) nationalism, i.e. placingthe interests of the Udmurts higher than the principle of class struggle; b) hostility to Russians or to Russian colonialism; c) antisovietism, i.e. hostility towards the power whose policy is not favourable to the Udmurts; d) sympathy towards other countries, i.e. Finland is seen as a model.

The deedthe prosecution brings forth against the accused are all derived from these ideological premises: everything they did since the Revolution is inspired by these ideas. So are interpreted Gerd"s different activities as an organiser, from the Association of Udmurt Culture Bölyakfounded in Moscow in 1923-24 (Kulikov 1991: 12) to the creation of the Udmurt writers" Union. But all of these acts are not condemnable per se. Here the prosecutors are compelled to rely on imagination and invention: the creation of SOFIN, the counterrevolutionary organisation, whose aim was to work for the interests of Finland and Estonia, in order to create a Finnish protectorate on Russia"s Finno-Ugric regions. The SOFIN counterrevolutionary organisation is an invention. But it is well documented: we would call it a network. They reconstructed a Finno-Ugric network that existed in a non-formal way and replaced weak, occasional links, with strong party-like affiliation subordinate relations. All this is a paranoiac construction, but it is quite well structured: all groups that were interested in Finno-Ugrianness were related.

Within this construction, Gerd and his companions not only follow their own ideological beliefs, but had sold themselves to the enemy; they are also paid by Finland and Estonia to transmit intelligence about Izhevsk weapon plant. It is clear that the most solid charges, the acts, are not consistent enough to rely on facts. Inventions are unavoidable.

The third component of the prosecution is about intention. As every act is illuminated by the ideological crimes, every act is potentially dangerous because of its possible consequences, i.e. the separation of the Finno-Ugric zones of the URSS in order to have them joining Finland. Words have no connection with reality. They have a meaning and a symbolic of their own. The verdict of the process was extremely severe: in a time where death penalty was rare, Gerd and his companion Yakovlev, whose sin was being a SR in the years following 1917, were actually condemned to death, while other "SOFIN members" were condemned to lighter camp penalties. Gerd" life, allegedly, was saved by Gor"ki"s interference, who very much appreciated the Udmurt poet [START_REF] Kuznetsov | Кузнецов, Николай Спиридонович. Из мрака[END_REF]: 67, Gerd 1998: 35). The death penalties were finally commuted into 10 years camps, and Gerd was in Solovki"s camp when the Great Terror operations led to his execution among thousands of other prisoners in Karelia, at a place called Sandomokh (Loriya1998: 152).

The other SOFIN accused have lighter penalties such as exile or some years in labour camps. The non-Udmurts are condemned to shorter periods in camp: the KomisLytkin, and Nalimov are respectively condemned to two years and liberated; Markelov is only exiled from Central Russia (Kulikov 1997: 238).

Conclusion

It is impossible to believe that Soviet authorities at the beginning of the 1930s were afraid of Finland in a territorial way. Hence this chargeand the identity of the accused shows that whatis under process is indeed Finno-Ugrianness, which is seen as a menace to Stalinist power. How can this be? The only possible explanation is a wish to control all kind of ethnicity more thoroughly that is had been done before.

At the beginning of the 1920, the central authorities had given free hands to the ethnic intellectuals to work for them and to develop innocuous cultures. In the 1930s the situation has changed. The Bolshevik power is well rooted. The Bolsheviks can start to implement their actual project, in which ethnicity is not an issue. It was perhaps an important point for part of the old Bolshevik leadership (as Lenin, who was himself from the Volga region), but not for those who have survived and for the majority of the party, which is strongly Russian-minded. Great-Russian chauvinism is not only a political ideology: it is a default position of most Russians, who do not even question the righteousness of their supremacy on other, different, less "civilised" ethnic groups. Everything that is aimed at supporting a non-Russian nation becomes suspect. This analysis is not in contradiction with the importance of ethnically structured country: it allowed Bolsheviks to keep ethnicity but only under thorough control and to turn it towards their own goals. Too independent minds are dangerous for this project, because they would not be satisfiedwith only national "form", and would demand corresponding content. The SOFIN"s operation had deep consequences especially on the Udmurt population: one part of the national intelligentsia was silenced by physical elimination, another by fear; others were morally compromised and had lost theirspiritual independence, although the few more years they had to live before they were also caught in the Great terror allowed some of them to produce important works for Udmurtness 29 . But the fear provoked by the SOFIN process answered in town to the fear caused by kulak repressions in the countryside: since 1928-1929, life was a succession of unpredictable blows. Gerd"s example showed that even writing conventional communist-minded works did not save from punishment. For Volga peoples, terror is part of life since collectivisation. For the succession of processes against Udmurts is fairly uninterrupted until the Great Terror. From the point of view of long-term political consequences, certainly collectivisation terror and intellectual terror against intellectuals are more relevant than the Great Terror: the latter was nothing new, fear had been long dominating the country, and while during the Great Terror repression touched indeed groups that had not been victimised in the previous years, they had lived as well under the empire of fear. Thus, the Great Terror did not bring anything totally new, except forits massiveness.

What are the conclusions we may draw from this experience?

-That the methods of the Great Terror had been thoroughly rehearsed 29 As, for example, writerMikhailKonovalov, whocould finish hisnovelGayan (1936) beforebeingarrested and eliminated.

-That the Great Terror was not an aberration, but a logical construct on the path Stalin had chosen since collectivisation -That border and war problematic are later phenomena. Ethnicity was dangerous as such. It had to be checked and subordinated to the State"s interests. -That the so called Lenin nationality policy that had structured the Soviet Union, while not being discussed as such, was a source of tension and one that was solved with the use of terror.

With the conquest of Kazan in 1552, the lands that formed previously the Kazan"s Khanate were absorbed by Russia.

TheCheremis wars in the 1560-1580; Ivan Bolotnikov"s (1605-7), Stepan Razin"s (1670-1671), EmelianPugachev"s revolts (1773-74). These last movements threatened directly the imperial power.

The Mordvins were (and are) divided between Erzya and Moksha Mordvins, whose languagesare still not immediately understandable for each other. They were much Russified and dispersed on a wide area.

Formerly called Cheremis. They were also divided into two groups speaking different dialects (fixed since the 1920s into two literary languages), the majority of Meadow Maris and a small active minority of Hill Maris and lived in a fairly compact area; while evangelised mostly between 1740 and 1767, they retained actively well into the 1930s animistic worldview and practices, which are being revitalised nowadays. Small groups of Maris had migrated eastwards to avoid heavy taxes and brutal Christianisation and they still dwell mostly in Bashkortostan.

This, for instance, KuzebayGerd, the main Udmurt poet, who was called to be the editor-in-chief of the party"s daily newspaper. He asserts: "The February Revolution writers changed immediately their orientation and passed unanimously to the camp of the new literature"(Gerd 1929: 21).

It is very clear in the case of the Udmurt executive commitee chairman TrofimBorisov, an ethnic Udmurt, physician and party member (for his biography, Pavlov 1991). He was expelled from the party by Izhevsk"s factory Russian lobby and accused of rape. While he was actually expelled from the Udmurt Communist Party, he was immediately after rehabilitated by the centre and sent as party leader in Kalmykia(Kulikov 1997: 42; Kuznetsov 1994: 27)

As emphasised by Isabelle Kreindler, Lenin, whose father was missionary school"s supervisor in the Volga region, might have been inspired by their implementation of vernacular languages" tuition, provided that the contents was Christian (Kreindler 1977).

In Russian:великодержавныйшовинизм.

In Russian:местныйнационализм.

Gerd wanted alse to receive the same kind of scholarship. But to him, some years later than for Lytkin, it was refused(Kuznetsov 1994:104).

Kralinahadjustdiscovered the existence of pre-warUdmurtliterature and that one of the main nameswasstill alive, living as an ophtalmologist in Alnashi, and sheaddressedher a letter.


Ivan Landjev
email: i.landjev@nbu.bg

Assia Rousseva

The Main Conjecture for Near-MDS Codes

Keywords: near-MDS codes, MDS codes, elliptic curves, (n, 3)-arcs, n-tracks, projective geometries

Introduction

Near-MDS have been introduced in 1995 in [START_REF] Dodunekov | On Near-MDS Codes[END_REF]. They are defined by weakening some restrictions in the definition of the MDS codes. The most popular definition is via generalized Hamming weights. A linear [n, k] q -code C is called a near-MDS code if

d i (C) = n -k + 1 for i = 2, . . . , k, d 1 (C) = n -k.
Of course, it is enough to require d 1 (C) = nk and d 2 (C) = nk + 2. From the properties of the generalized Hamming weights one can easily deduce that the dual of a near-MDS code is again a near-MDS code. The following propositions characterize near-MDS codes and can serve as alternative definitions. The proofs can be found in [START_REF] Dodunekov | On Near-MDS Codes[END_REF].

Proposition 1. A linear [n, k] q -code C is a near-MDS code if and only if any parity-check matrix H C of C satisfies the conditions:

(1) any nk -1 columns of H C are linearly independent;

(2) there exist nk linearly dependent columns;

(3) any nk + 1 columns of H C are of rank nk.

Proposition 2. A linear [n, k] q -code C is near-MDS if and only if any generator matrix G C of C satisfies the conditions:

(1) any k -1 columns of G C are linearly independent;

(2) there exist k linearly dependent columns;

(3

) any k + 1 columns of G C are of rank k. Proposition 3. A linear [n, k] q code is a near-MDS code if and only if d(C) + d(C ⊥ ) = n.
Closely related to near-MDS codes are the so-called almost-MDS codes introduced by de Boer [START_REF] De Boer | Almost MDS Codes, Designs[END_REF][START_REF] De Boer | Codes: their parameters and Geometry[END_REF]. Almost-MDS are defined as [n, k] q -codes with minimum distance d = nk, or, in other words, as codes with Singleton defect 1. Not every almost-MDS code is near-MDS, as pointed out in [START_REF] Dodunekov | On Near-MDS Codes[END_REF], but for large n both notions coincide.

Proposition 4. If n > k + q every [n, k, n -k] q -code is a near-MDS code.
The weight distribution of a near-MDS code can be determined up to a single parameter. In the theorem below it is taken to be the number of words of minimal weight.

Theorem 1. Let C be an [n, k] q near-MDS code. Let (A i ) and (A ′ i ) be the spectra of C and C ⊥ , respectively. Then

A n-k+s = n k -s s-1 j=0 (-1) j n -k + s j (q s-j -1) + (-1) s k s A n-k ,
where s = 1, . . . , k, and

A ′ k+s = n k + s s-1 j=0 (-1) j k + s j (q s-j -1) + (-1) s n -k s A ′ k ,
where s = 1, . . . , nk.

For almost-MDS codes the situation is more complicated. The numbers of the parameters depends on the Singleton defect of the orthogonal code (cf. [START_REF] Faldum | Codes of Small Defect[END_REF]). Theorem 1 gives a simple upper bound on the number of words of minimal weight.

Corollary 1. For an [n, k] q near-MDS code

A n-k ≤ n k -1 q -1 k ,
with equality if and only if A n-k+1 = 0. By duality,

A ′ k ≤ n k + 1 q -1 n -k ,
with equality if and only if A ′ k+1 = 0.

The Geometric View at Near-MDS Codes

It is known that with every [n, k, d] q -code of full length one can associate a multiset of points in PG(k -1, q) (possibly in a non-unique way) so that isomorphic codes are associated with projectively equivalent multisets (cf. [START_REF] Dodunekov | Codes and projective multisets[END_REF]). This implies that the existence of an [n, k] q near-MDS code is equivalent to that of a set K of points in PG(k -1, q) with the following properties:

(1) every k -1 points from S are in general position (generate a hyperplane) (2) there exist k points from S that lie in a hyperplane (3) every k + 1 points from S generate PG(k -1, q).

In particular, if k = 3 a near-MDS code is equivalent to an (n, 3)-arc in PG(2, q). The nonexistence of maximal (n, 3)-arcs, i.e. arcs with n = 2q + 3 was ruled out originally by Thas [START_REF] Thas | Some results concerning {(q+1)(n-1); n}-arcs and {(q+1)(n-1)+1; n}arcs in finite projective planes of order q[END_REF]. This result is a part of a more general theorem about the nonexistence of maximal arcs in PG(2, q) for odd q proved by Ball, Blokhuis and Mazzocca [START_REF] Ball | An easier proof of the maximal arcs conjecture[END_REF][START_REF] Ball | Maximal arcs in Desarguesian planes of order q do not exist[END_REF]. Since every (2n + 2, 3)-arc is extendable one gets that the size of an (n, 3)-arc is bounded by n ≤ 2q + 1. This provides the best upper bound on the length of a near-MDS code (cf. Theorem 2(vi)).

Almost-MDS codes are equivalent to so-called n-tracks. An n-track is a set of points in PG(r, q) such that every r of them are in general position. Tables containing exact values and bounds on the maximal size of an n-track are contained in [START_REF] Alderson | Maximal AMDS Codes[END_REF][START_REF] De Boer | Almost MDS Codes, Designs[END_REF][START_REF] De Boer | Codes: their parameters and Geometry[END_REF][START_REF] Hirschfeld | The packing problem in statistics, coding theory and finite projective spaces: update 2001[END_REF].

Near-MDS Codes over Small Fields

With no loss of generality, we consider only codes with k ≤ 2q and n ≥ 2k. Near-MDS codes of dimension greater than n 2 are obtained as orthogonal to near-MDS codes with k ≤ n 2 .

In the binary case we can list all near-MDS codes. These are the extended Hamming [START_REF] De Boer | Almost MDS Codes, Designs[END_REF][START_REF] Ball | An easier proof of the maximal arcs conjecture[END_REF][START_REF] Ball | An easier proof of the maximal arcs conjecture[END_REF]-code, the simplex [START_REF] Bartoli | The non-existence of some NMDS codes and the extremal sizes of complete (n, 3)-arcs in P G(2, 16)[END_REF][START_REF] Alderson | Maximal AMDS Codes[END_REF][START_REF] Ball | An easier proof of the maximal arcs conjecture[END_REF]-code, the [6, 3, 3]-codes obtained by shortening the Hamming code of length 7, as well as, several trivial codes of dimensions one and two.

In the ternary case, we have one [START_REF] De Boer | Codes: their parameters and Geometry[END_REF][START_REF] Alderson | Maximal AMDS Codes[END_REF][START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF] 3 -code associated with the affine plane AG(2, 3), one [START_REF] Boukliev | Some New Results on Optimal Codes over F5, Designs[END_REF][START_REF] Ball | An easier proof of the maximal arcs conjecture[END_REF][START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF] 3 -code, one [START_REF] Dodunekov | On Near-MDS Codes[END_REF][START_REF] Ball | Maximal arcs in Desarguesian planes of order q do not exist[END_REF][START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF] 3 -code (the orthogonal to the Golay code) and one [START_REF] Dodunekov | On the quaternary[END_REF][START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF][START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF] 3 -code (the extended ternary Golay code).

For codes over F 4 , there exist three non-isomorphic [START_REF] De Boer | Codes: their parameters and Geometry[END_REF][START_REF] Alderson | Maximal AMDS Codes[END_REF][START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF] 4 -codes, associated with the three non-equivalent (9, 3)-arcs in PG [START_REF] Abatangelo | Elliptic near-MDS codes[END_REF][START_REF] Ball | An easier proof of the maximal arcs conjecture[END_REF], two [START_REF] Boukliev | Some New Results on Optimal Codes over F5, Designs[END_REF][START_REF] Ball | An easier proof of the maximal arcs conjecture[END_REF][START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF] 4 -codes, exactly one [START_REF] Dodunekov | On Near-MDS Codes[END_REF][START_REF] Ball | Maximal arcs in Desarguesian planes of order q do not exist[END_REF][START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF] 4 -code and exactly one [START_REF] Dodunekov | On the quaternary[END_REF][START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF][START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF] 4 -code [START_REF] Dodunekov | On the quaternary[END_REF][START_REF] Dodunekov | Near-MDS Codes over Some Small Fields[END_REF]. It should be noted that the [START_REF] Dodunekov | On the quaternary[END_REF][START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF][START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF] 4 was constructed by Dumer-Zinoviev in [START_REF] Dumer | Some New Maximal Codes over GF(4)[END_REF] as the first member of an infinite family of uniformly packed codes. Remarkably, this code yields a cascade representation of the extended binary Golay code.

There exist two non-isomorphic [START_REF] Dodunekov | On Near-MDS Codes[END_REF][START_REF] Alderson | Maximal AMDS Codes[END_REF][START_REF] De Boer | Almost MDS Codes, Designs[END_REF] 5 codes associated with the two (11, 3)arcs in PG [START_REF] Abatangelo | Elliptic near-MDS codes[END_REF][START_REF] Ball | Maximal arcs in Desarguesian planes of order q do not exist[END_REF]. One of them extends to a [START_REF] Dodunekov | On the quaternary[END_REF][START_REF] Ball | An easier proof of the maximal arcs conjecture[END_REF][START_REF] De Boer | Almost MDS Codes, Designs[END_REF] 5 code which cannot be further extended. A [START_REF] Dodunekov | On the quaternary[END_REF][START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF][START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF] 5 -code does exist. It was constructed in [START_REF] Boukliev | Some New Results on Optimal Codes over F5, Designs[END_REF] using a computer. Later on, Abatangelo and Larato [START_REF] Abatangelo | Elliptic near-MDS codes[END_REF] constructed six non-isomorphic codes with these parameters. They extended by two points the elliptic curve Γ 6 of degree 6 in PG(5, q) arising from a non-singular cubic curve of PG(2, q) via the canonical Veronese embedding

ν : (X : Y : Z) → (X 2 : XY : Y 2 : XZ : Y Z : Z 2 ).

Near-MDS Codes of Maximal Length

Let us denote by m ′ (k, q) the maximum possible length for which there exists a [n, k] q near-MDS code. The following theorem summarizes some straightforward observations about m ′ (k, q). Theorem 2. Let k be a positive integer and let q be a prime power. Then (i) m ′ (2, q) = 2q + 2;

(ii) m ′ (k, q) ≤ m ′ (kα, q) + α, for every α with 0 ≤ α ≤ k;

(iii) m ′ (k, q) = k + 1 for k > 2q;

(iv) m ′ (2q, q) = 2q + 2;

(v) m ′ (2q -1, q) = 2q + 1.

(vi) m ′ (k, q) ≤ 2q + k -2;

Near-MDS codes with parameters [n, k] q can be constructed from elliptic curves over F q having exactly n rational points [START_REF] Tsfasman | Algebraic-Geometric Codes[END_REF] (cf. also [START_REF] Abatangelo | Near-MDS codes arising from algebraic curves[END_REF][START_REF] Abatangelo | Elliptic near-MDS codes[END_REF][START_REF] Giulietti | On the extendability of Near-MDS elliptic codes[END_REF][START_REF] Guilietti | On the completeness of certain n-tracks arising from elliptic curves[END_REF]). Such codes are referred to as elliptic codes. For every prime power q = p r , p a prime, near-MDS codes exist for lengths up to N q (1), where N q (1) denotes the maximum number of F q -rational points an elliptic curve defined over F q can have. By a result of Waterhouse [START_REF] Waterhouse | Abelian varieties over finite fields[END_REF], we know that for every q = p e N q (1) = q + ⌊2 √ q⌋ for p|⌈2 √ q⌉ and odd e, q + ⌊2 √ q⌋ + 1 otherwise.

Due to extensive computational work by Bartoli, Marcugini, Milani and Pambianco [START_REF] Bartoli | The non-existence of some NMDS codes and the extremal sizes of complete (n, 3)-arcs in P G(2, 16)[END_REF][START_REF] Dodunekov | Near-MDS Codes over Some Small Fields[END_REF][START_REF] Marcugini | NMDS codes of maximal length over Fq, 8 ≤ q ≤ 11[END_REF][START_REF] Marcugini | Classification of linear codes exploting an invariant[END_REF], the exact values of m ′ (k, q) were determined for all fields of order q ≤ 9, as well as lower and upper bounds on the size of the longest near-MDS code for some larger fields. Even more results were obtained for the case of dimension three, which corresponds to the problem of the maximal size of an (n, 3)-arc in PG(2, q) (cf [START_REF] Marcugini | Maximal (n, 3)-arcs in PG(2, 11[END_REF][START_REF] Marcugini | Classification of the (n, 3)-arcs in PG(2, 7)[END_REF][START_REF] Marcugini | Maximal (n, 3)-arcs in PG[END_REF]). These results are summarized in the table below. According to Theorem 2(vi), we have m ′ (k, q) ≤ 2q + k -2. It can be seen from the table above that equality is achieved for several pairs (k, q). The following theorem gives an improvement over Theorem 2(vi) for sufficiently large dimensions.

q/k 2
Theorem 3. There exist no [2q + k -2, k] q near-MDS codes for k ≥ q + 4 and q ≥ 9.

Proof. We are going to use the geometric interpretation of near-MDS codes. Fix an integer q + 4 < k < q + √ q + 3. Let K be an arc with 2q + k -2 points in PG(k -1, q), associated with a [2q + k -2, k] q near-MDS code. Furthermore, let P 1 , . . . , P k-2 be points from K. By the properties of the arcs associated with near-MDS codes, these k -2 points are in general position. Set S = P 1 , P 2 , . . . , P k-2 , S i = P 1 , . . . , P i-1 , P i+1 , . . . , P k-2 , i = 1, . . . , k -2.

Obviously, dim S = k -3, and dim S i = k -4. Let H be a hyperplane in PG(k -1, q) which does not contain any of the points P 1 , . . . , P k-2 .

At first, we are going to prove that there exists a point Q ∈ S ∩ H which is not contained in any of the subspaces S i . Assume for a contradiction that such a point Q does not exist and the subspaces S i cover all points of S ∩ H. This means that the subspaces S i ∩ H also cover all points of S ∩ H. By duality, we get that there exist k -2 points in S ∩ H, the dual space to S ∩ H, that block all hyperplanes. By the restriction on k, we have that k -2 < q + √ q + 1, and a well-known result of Heim [START_REF] Heim | Blockierende Mengen in endlichen projecktiven Räumen[END_REF] implies that this blocking set should contain a line. In other words, the subspaces S i meet in a subspace of codimension 2 in S. This is a contradiction, because ∩ k-2 i=1 S i = ∅. This follows from the fact that the points P 1 , . . . , P k-2 are in general position. Now we can construct a plane π in H which does not meet any of the subspaces S i . Fix a line L in H which is disjoint from S ∩ H. The existence of such a line follows from the dimension formula. The plane π = L, Q meets S only in the point Q and is therefore disjoint from any subspaces S i . Note that from the properties of the near-MDS codes and the arcs associated with them |K ∩ π| ≤ 3. Now consider a projections ϕ i , i = 1, . . . , k -2, from each S i to π given by

ϕ i : P \ S i → π P → S i , P ∩ π ,
where P is the set of points of PG(k -1, q). Obviously, all induced arcs K ϕi are plane arcs with parameters (2q + 1, 3).

If P ∈ K ∩ π, then P is contained in all induced arcs. Obviously Q = S ∩ π is also contained in all arcs K ϕi . Note that there are at most three such points. If R is a point from π which is contained neither in K nor in S, then it is contained in at most two of K ϕi (since a hyperplane contains at most k points from K).

Counting the pairs (P, K ϕi ) with P ∈ K ϕi in two possible ways, we get (k -2)(2q + 1) ≤ 2(q 2 + q -3) + 4(k -2), whence k ≤ q + 4, a contradiction. Now it remains to use Theorem 2(ii) to obtain the nonexistence for all dimensions k > q + 4.

Let us note that the proof of the nonexistence of (2q + 1, 3)-arcs would immediately imply the nonexistence of [2q + k -2, k] q near-MDS codes. All numerical evidence suggests that this is true for all q ≥ 8, but no proof of the nonexistence of (2q + 1, 3)-arcs in PG(2, q) for large q seems to be known for the time being. There is a problem for (n, 3)-arcs in PG(2, q) suggested by A. Blokhuis asking to determine a constant c such that n/q < c < 2 for q large enough, or a construction where n/q > c > 1 [START_REF] Ball | Bounds on (n, r)-arcs and their application to linear codes[END_REF].

We finish with two conjectures for near-MDS codes that are similar to the famous Main Conjecture for MDS codes.

Weak Main Conjecture for NMDS codes. For all positive integers k and all prime powers q it holds that m ′ (k, q) ≤ 2(q + 1).

Strong Main Conjecture for NMDS codes.

There exists a universal constant c (not depending on q) such that m ′ (k, q) ≤ N 1 (q) + c.

Acknowledgments. This research has been supported by the Research Fund of Sofia University.


Emanuele Bellini
email: eemanuele.bellini@gmail.com

Alessio Meneghetti

On the Griesmer bound for nonlinear codes

Most bounds on the size of codes hold for any code, whether linear or nonlinear. Notably, the Griesmer bound holds only in the linear case. In this paper we identify code parameters (q, d, k) for which the Griesmer bound holds also in the (systematic) nonlinear case. Moreover, we show that the Griesmer bound does not necessarily hold for a systematic code by showing explicit counterexamples.

On the other hand, we are also able to provide some versions of the Griesmer bound holding for all systematic codes.

Introduction

We consider codes over a finite field F q of length n, with M codewords, and distance d. A code C with such parameters is denoted as an (n, M, d) q -code.

Definition 1. An (n, q k , d) q -systematic code C is the image of a map F : (F q ) k → (F q ) n , n ≥ k, s.t. a vector x = (x 1 , . . . , x k ) ∈ (F q ) k is mapped to a vector (x 1 , . . . , x k , f k+1 (x), . . . , f n (x)) ∈ (F q ) n , where f i , i = k + 1, . . . , n, are maps from (F q ) k to F q . We refer to k as the dimension of C. The coordinates from 1 to k are called systematic, while those from k + 1 to n are called non-systematic.

If the maps f i are all linear, then the systematic code C is a subspace of dimension k of (F q ) n and we say it is a [n, k, d] q -linear code. A nonlinear code is a code that is not necessarily linear or systematic.

We denote with len(C), dim(C), d(C), respectively, the length, the dimension (when defined) and the minimum distance of a code C.

Recent results on systematic codes can be found in [AB08] and [AG09], where it is proved that if a linear code admits an extension, then it admits also a linear extension.

This implies that if a systematic code C can be puntured obtaining a linear code, then there exists a linear code with the same parameters of C.

A central problem of coding theory is to determine the minimum value of n for which an (n, M, d) q -code or an [n, k, d] q -linear code exists. We denote by N q (M, d) the minimum length of a nonlinear code over F q , with M codewords and distance d. We denote by S q (k, d) the same value in the case of a systematic code of dimension k, while we use L q (k, d) in the case of a linear code of dimension k. Observe that

N q q k , d ≤ S q (k, d) ≤ L q (k, d).
A well-known lower bound for L q (k, d) is

Theorem 1 (Griesmer bound). All [n, k, d] q linear codes satisfy the following bound:

n ≥ L q (k, d) ≥ g q (k, d) := k-1 i=0 d q i (1)
The Griesmer bound was introduced by Griesmer [Gri60] in the case of binary linear codes and then generalized by Solomon and Stiffler [SS65] in the case of q-ary linear codes. It is known that the Griesmer bound is not always sharp [Van80].

Important examples of linear codes meeting the Griesmer bound are the simplex code

[HP03] (Section 1.8) and the [5,6,11] 3 Golay code [HP03] (Section 1.9).

Many authors such as [Mar97] and [Kle04], have identified classes of linear codes meeting the Griesmer bound. In particular, finite projective geometries play an important role in the study of these codes. Many known bounds on the size of nonlinear codes, for 2 When the Griesmer bound holds for systematic codes

The following proposition and lemma are well-known.

Proposition 1. Let C be an (n, q k , d) q -systematic code, and C be the code obtained by shortening C in a systematic coordinate. Then C is an (n -1, q k-1 , d ) q -systematic code with d ≥ d.

Lemma 1. If n > k, then given an (n, q k , d) q -systematic code C, there exists an

(n, q k , d) q -systematic code C for any 1 ≤ d ≤ d.
Theorem 2. For fixed q and d, if

S q (k, d) ≥ g q (k, d) (2)
for all k such that 1 ≤ k < 1 + log q d, then (2) holds for any positive k.

Proof. It is sufficient to show that if an (n, q k , d) q -systematic code not satisfying the Griesmer bound exists, then an (n , q k , d) q -systematic code not satisfying the Griesmer bound exists with k < 1 + log q d, and n > k .

For each fixed d, q suppose there exists

k such that S q (k, d) < g q (k, d). Let us call Λ q,d = {k ≥ 1 | S q (k, d) < g q (k, d)}. If Λ q,d
is empty then the Griesmer bound is true for such parameters q, d. Otherwise there exists a minimum k ∈ Λ q,d such that S q (k , d) < g q (k , d). In this case we can consider an (n, q k , d) q systematic code C

with n = S q (k , d). We build a new code C by shortening C in a systematic coordinate.

Clearly, C is an (n -1, q k -1 , d ) q systematic code and d ≥ d. Applying Lemma 1 to C , we can obtain an (n -1, q k -1 , d) q systematic code C. Since k was the minimum among all the values in Λ q,d , the Griesmer bound holds for C, and so

n -1 ≥ g q (k -1, d) = k -2 i=0 d q i . (3)
We observe that, if

q k -1 ≥ d, then d q k -1 = 1, so we can rewrite (3) as n ≥ k -2 i=0 d q i + 1 ≥ k -2 i=0 d q i + d q k -1 = k -1 i=0 d q i = g q (k , d)
Since we supposed n < g q (k , d), we have reached a contradiction.

Set of parameters for which the Griesmer bound holds in the nonlinear case

In this section we identify several sets of parameters (q, d) for which the Griesmer bound holds for systematic codes.

Theorem 3. If d ≤ 2q then S q (k, d) ≥ g q (k, d).
Proof. First, consider the case d ≤ q. By Theorem 2 it is sufficient to show that, fixing q, d, for any n an (n, q k , d) q -systematic code with 1 ≤ k < 1 + log q d and n < g q (k, d)

does not exist. If 1 ≤ k < 1 + log q d then log q d ≤ log q q = 1, and so k may only be 1. Since g q (1, d) = d and n ≥ d, we clearly have that n ≥ g q (1, d).

Now consider the case q < d ≤ 2q. If 1 ≤ k < 1 + log q d then log q d ≤ log q 2q = 1 + log q 2, and so k can only be 1 or 2. We have already seen that if k = 1 then n ≥ g q (k, d) for any n, so suppose k = 2. If an (n, q 2 , d) q -systematic code C exists with n < 1 i=0 d q i = d+2, then by the Singleton bound we can only have n = d+1. Therefore C must have parameters (d + 1, q 2 , d).

In [Hil86,Ch. 10] it is proved that a q-ary (n, q 2 , n -1) q code is equivalent to a set of n -2 mutually orthogonal Latin squares (MOLS) of order q (Theorem 10.20), and that there are at most q -1 Latin squares in any set of MOLS of order q (Theorem 10.18).

In our case n = d + 1 > q + 1, therefore n -2 > q -1. The existence of C would imply the existence of a set of more than q -1 MOLS, which is impossible.

Theorem 4 (Plotkin bound). Consider an (n, M, d) q code, with M being the number of codewords in the code.

If n < qd q-1 , then M ≤ d/(d -(1 -1/q)n), or equivalently n ≥ d((1 -1/M )/(1 -1/q)).
Proposition 2. Let r be a positive integer, then N q (q k , q k-1 r) ≥ g q (k, q k-1 r).

Proof. Suppose there exists an (n, q k , q k-1 r) q -code C that does not satisfy the Griesmer bound. Hence n < k-1 i=0 q k-1 r q i

. Observe that in this case

k-1 i=0 q k-1 r q i = k-1 i=0 q k-1 r q i = q k-1 r k-1 i=0 1 q i . Since k-1 i=0
1 q i = 1-1 q k 1-1 q , we obtain n < q k-1 r 1 -1/q k 1 -1/q . ( 4
)
We also observe that n < q k-1 r (1 -1/q k )/(1 -1/q) < q k-1 r (1/(1 -1/q)) = d/(1 -1/q), and we can write this inequality as n < dq q-1 , which is the hypothesis for the Plotkin bound. Applying Theorem 4, we get

q k ≤ d d-n(1-1/q) ≤ d d-n(1-1/q) , i.e. n ≥ d 1-1/q k
1-1/q , which contradicts equation ( 4). Hence each (n, q k , q k-1 r) q -code satisfies the Griesmer bound.

Note that Proposition 2 is not restricted to systematic codes, but it holds for nonlinear codes with at least q k codewords, as the next corollary explains.

Corollary 1. Let M ≥ q k and let r be a positive integer. Then N q (M, q k-1 r) ≥ g q (k, q k-1 r).

Lemma 2. Let q be fixed, d = q l r for a certain r such that 1 ≤ r < q and l ≥ 0, and let k be such that q k-1 ≤ d. Then N q (q k , d) ≥ g q (k, d).

Proof. Since 1 ≤ r < q, the hypothesis q k-1 ≤ d is equivalent to k -1 ≤ l. We use Proposition 4 and we set h

= min(k -1, l), obtaining n ≥ k-1 i=0 d q i .
Theorem 5. Let 1 ≤ r < q and l a positive integer. Then S q (k, q l r) ≥ g q (k, q l r).

Proof. To prove that the Griesmer bound is true for these particular choices of d we use Theorem 2, hence we only need to prove that the Griesmer bound is true for all choices of k such that q k-1 ≤ d.

We now use Lemma 2, which ensures that all such codes respect the Griesmer bound.

Corollary 2. Let q = 2 and let l be a positive integer, then S 2 (k, 2 l ) ≥ g 2 (k, 2 l ). We need the following numerical lemmas, whose proofs we omit and are present in

g 2 (k, d + 1) = g 2 (k, d) + min(k, l + 1), ( 5
)
where l is the maximum integer such that 2 l divides d.

Lemma 5. If k ≤ r, then g 2 (k, 2 r ) < 2 r+1 .
Theorem 6. Let r and s be two positive integers such that r > s, and let d = 2 r -2 s .

Then

S 2 (k, d) ≥ g 2 (k, d).
Proof. If r = s + 1, then 2 r -2 s = 2 s , hence we can apply Corollary 2 and our claim holds. Therefore we can assume r > s + 1 in the rest of the proof. Suppose there exists s < r s.t. S 2 (k, 2 r -2 s ) < g 2 (k, 2 r -2 s ), i.e. the Griesmer bound does not hold for an (n, 2 k , d) 2 -systematic code C, with d = 2 r -2 s and n = S 2 (k, d). Due to Theorem 2, we can consider the case k < 1 + log 2 d, and so

k ≤ r. Let m = n/d. For C m = S 2 (k, 2 r -2 s ) 2 r -2 s ≤ g 2 (k, 2 r -2 s ) -1 2 r -2 s
We claim that m < g 2 (k, 2 r )/(2 r ). First we observe that if k ≤ r, then

g 2 (k, 2 r ) 2 r = k-1 i=0 1 2 i = 2 1 - 1 2 k .
We consider now the ratio m:

m ≤ g 2 (k, 2 r -2 s ) -1 2 r -2 s = 1 2 r -2 s k-1 i=0 2 r -2 s 2 i - 1 2 r -2 s (6)
We start from the case k ≤ s + 1, and we can write (6) as

m < 1 2 r -2 s k-1 i=0 2 r -2 s 2 i = k-1 i=0 1 2 i = 2 1 - 1 2 k , so m < g 2 (k, 2 r )/(2 r ).
We consider now the case k > s + 1, and we write our claim in an equivalent way:

2 r (g 2 (k, 2 r -2 s ) -1) < (2 r -2 s )g 2 (k, 2 r ).
Rearranging the terms we obtain

2 s g 2 (k, 2 r ) < 2 r (g 2 (k, 2 r ) -g 2 (k, 2 r -2 s ) + 1), (7)
and we focus on the difference g 2 (k, 2 r ) -g 2 (k, 2 r -2 s ). For any d in the range 2 r -2 s ≤ d < 2 r we can apply Lemma 4, observing that d = 2 l r where l ≤ s, and this implies k > l + 1. We obtain g 2 (k, d + 1) = g 2 (k, d ) + l + 1. Applying it for all distances from 2 r -2 s till we reach 2 r we obtain

g 2 (k, 2 r ) -g 2 (k, 2 r -2 s ) = 2 s+1 -1 (8)
We substitute now (8) into (7), which becomes

2 s g 2 (k, 2 r ) < 2 r • 2 s+1 =⇒ g 2 (k, 2 r ) < 2 r+1 ,
and this is always true provided k ≤ r, as shown in Lemma 5.

We now consider the (tn, 2 k , td) 2 -systematic code C t obtained by repeating t times the code C. We remark that the value m can be thought of as the slope of the line d(C t ) → len(C t ), and we proved that m < g 2 (k, 2 r )/(2 r ). On the other hand, since k ≤ r we can apply Lemma 3, which ensures that g 2 (k, 2 r+b ) = 2 b g 2 (k, 2 r ), namely the Griesmer bound computed on the powers of 2 is itself a line, and its slope is strictly greater than m. Due to this we can find a pair (t, b) such that td > 2 b and tn < g 2 (k, 2 b ). This means that we can find a systematic code C with distance greater than 2 b and length smaller than g 2 (k, 2 b ). We can apply Lemma 1, and find a systematic code with the same length of C and distance equal to 2 b . This contradicts Corollary 2, hence for each k ≤ r we have

S 2 (k, 2 r -2 s ) ≥ g 2 (k, 2 r -2 s ). Finally, observe that k ≤ r implies k ≤ log 2 (2 r ) = log 2 (2 r -2 s ) < 1 + log 2 d, so
we can apply Theorem 2 and conclude.

Corollary 3. Let r and s be two positive integers such that r > s, and let d = 2 r -1

or d = 2 r -2 s -1. Then S 2 (k, d) ≥ g 2 (k, d).
Proof. We give the proof for the case d = 2 r -2 s -1, the same argument can be applied to the other case by applying Corollary 2 instead of Theorem 6.

Suppose S 2 (k, d) < g 2 (k, d), i..e. there exists an (n, k, d) 2 -systematic code for which n < g 2 (k, d).

We can extend such a code to an (n+1, k, d+1) 2 -systematic code C by adding a parity check component to each codeword. Then C has distance d(C) = d + 1 = 2 r -2 s , so we can apply Theorem 6, finding n + 1 ≥ g 2 (k, d + 1). Observe that d is odd, so applying Lemma 4 we obtain

n + 1 ≥ g 2 (k, d + 1) = g 2 (k, d) + 1 =⇒ n ≥ g 2 (k, d),
which contradicts (9).

Versions of the Griesmer bound holding for nonlinear codes

In this section we provide some versions of the Griesmer bound holding for any systematic code, whose proofs we omit and can be found in [BGMS15]. For systematic codes we can improve the Singleton bound as follows.

Proposition 3. Let k and d be any positive integers, then

S 2 (k, d) ≥ k + 3 2 d -2.
We derive from Theorem 5 a weaker version of the Griesmer bound holding for any systematic code.

Remark 1. Considering an integer d, there exist 1 ≤ r < q and l ≥ 0 such that q l r ≤ d < q l (r + 1) ≤ q l+1 . (10)

In particular, l has to be equal to log q d , and from inequality (10) we obtain d/q l -1 < r ≤ d/q l , namely r = d/q l . Corollary 4 (Bound A). Let l = log q d and r = d/q l . Then

S q (k, d) ≥ d + k-1 i=1 q l r q i .
Next we generalize Proposition 2.

Proposition 4. Let q, k and d be fixed, and let l be the maximum integer such that q l divides d. Then

N q (q k , d) ≥ h i=0 d q i ,
where h is the minimum between k -1 and l.

Corollary 5 (Bound B). Let q, M and d be fixed, let k be the maximum integer such that q k ≤ M , and let l be the maximum integer such that q l divides d. Then

N q (M, d) ≥ h i=0 d q i ,
where h is the minimum between k -1 and l.

We consider now the following bounds, which can be seen as weaker versions of the Griesmer bound or as an extension of the Plotkin bound.

Proposition 5. For each choice of q, k and d, we have

N q (q k , d) ≥ k-1 i=0 d q i = d 1 -1 q k 1 -1 q .

  example the Johnson bound ([Joh71]), the Plotkin bound ([Plo60], the Bellini-Guerrini-Sala bound ([BGS14]) and the Linear Programming bound ([Del73]), are true for both linear and nonlinear codes.

[

  Let r be a positive integer, and let k ≤ r+1. Then g 2 (k, 2 r+1 ) = 2g 2 (k, 2 r ). Lemma 4. For each k and d it holds

the following Corollary.

Corollary 6 (Bound C). For each choice of q, k and d,

where k is the larger integer such that M ≥ q k .

5 Counterexamples to the Griesmer bound We consider the cyclic code C l of length 15 associated to the complete defining set S = {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12}, which is a code with 16 codewords and distance 8.

We obtain a new code C by concatenating each codeword in C l with a different codeword in C. In this way C is an (34,16,18) 2 -systematic code. Since g 2 (4, 18) = 35, S 2 (4, 18) < g 2 (4, 18), proving that the Griesmer bound is in general not true for systematic codes (for details, see [BGMS15]).

Aknowledgements

The authors would like to thank Eleonora Guerrini and Massimiliano Sala. The authors would also like to thank the anonymous reviewer for interesting comments.


Alexander Shishkin
email: sisoid@frtk.ru

Multicomponent Network Codes for a Channel with Random Linear Transformations and Packet Errors

This work is related to new multicomponent network codes for a channel with random linear transformations and packet errors. New code construction is a generalization of Gabidulin-Pilipchuk codes, and similarly uses rank codes with restrictions as subcodes. Usage of a greedy algorithm, when selecting the code components, allows us to increase code cardinality compared with the previously known constructions. We provide the conditions under which the described multicomponent code can correct both erasures and packet errors in the channel. Finally, we present an efficient algorithm of decoding both types of errors and give some examples.

Introduction

Consider K q -a finite field of q elements. Construct an n-dimensional vector space, K n q , with elements from K q , and denote the set of all its subspaces as A(n). A subspace V of dimension k ≤ n from A(n) is the set of q k vectors with length n and elements from K q .

The subspace V may be considered as a linear span over k vectors from K n q , or, equivalently, over some k × n matrix with the elements from K q . Thus, every k × n matrix V , with the elements from K q , uniquely determines some k-dimensional subspace V from A(n). However, every subspace from A(n) may have several generating matrices: multiplying matrix V by a nonsingular k × k matrix, T , gives a k × n matrix Ṽ = T V that generates the same subspace as the matrix V .

In connection with this, it is convenient to specify the subspaces with the matrices in reduced row echelon form, to which an arbitrary matrix of size k × n can be brought using the Gaussian elimination procedure. The reduced row echelon form of a matrix is characterized by the following properties:

-The first nonzero element in every row equals 1 q . It is called the leading element of the row. -Every leading element is the only nonzero element in its column.

-The leading element of the next line is always located to the right of the leading element of the previous line.

-There are no restrictions on the remaining matrix elements. They are called free elements.

One can establish a bijection between k-dimensional subspaces from A(n) and k × n matrices over K q in reduced row echelon form. The location of the leading elements of a k × n matrix in reduced row echelon form can be described by a multi-index I = {i 1 , i 2 , . . . , i k }, defined as the set of integers corresponding to the column numbers in which the leading elements are located. Another way to describe the location of leading elements is a vectorindex v of length n, which contains ones in those components that correspond to the columns with leading elements, and zeros in the other components.

For example, the 5 × 12 matrix U from equation 1, which is in reduced row echelon form, can be described by the multi-index U I = {2, 3, 7, 11, 12} or vector-index U v = (011000100011).

U =       0 1 0 * * * 0 * * * 0 0 0 0 1 * * * 0 * * * 0 0 0 0 0 0 0 0 1 * * * 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1       . ( 1
)
Note that symbols '*' correspond to the free elements of the matrix U .

Subspace codes

Between any two subspaces from A(n), the Grassmannian distance can be introduced as:

d sub (U, V) = dim(U ∪ V) -dim(U ∩ V). (2)
Let U be a subspace of dimension m with the generating matrix U , and V be a subspace of dimension k with the generating matrix V . Then the Grassmannian distance between U and V can be calculated as follows:

d sub (U, V) = 2rank U V -m -k. (3)
When both subspaces have the same dimension (m = k) the distance d sub will be even for any U and V.

Using the Grassmannian distance, the concept of subspace codes can be introduced. Subspace [n, M, d sub , k]-code is a set of k-dimensional subspaces from A(n), which contains M elements, and the distance between any two subspaces is not less than d sub . There is the Johnson-type upper bound on the cardinality of the subspace code [START_REF] Xia | Johnson type bounds on constant dimension codes // Designs[END_REF]:

M ≤ q n -1 q k -1 q n-1 -1 q k-1 -1 • • • q n-k+δ -1 q δ -1 • • • , (4)
where δ = d sub /2. Subspace codes are widely used in network coding theory. An important task in the construction of subspace codes is to maximize the cardinality M at a fixed correcting capability of a code, determined by the subspace distance d sub .

Grassmannian distance is closely related to the rank distance used in the construction of rank-metric codes [START_REF] Gabidulin | Theory of Codes with Maximum Rank Distance[END_REF]. Let U and V be subspaces of dimension k with generating matrices U and V , which are in reduced row echelon form. To illustrate the connection of subspace codes with the rank codes we introduce the concept of a submatrix of the leading elements. For the matrix U , in reduced row echelon form, the set of its columns containing the leading elements is called the submatrix of the leading elements and is denoted by U l . The set of all the remaining columns is called the submatrix of the free elements and is denoted by U f . Note that U f contains all the free elements of the matrix U , but not each of its elements is free. Further, there are two possibilities.

If multi-indices U I and V I are equal, then the leading elements matrices of U and V are equal too, and the Grassmannian distance between U and V can be written as follows:

d sub (U, V) = 2rank U V -2k = 2rank U l |U f V l |V f -2k = = 2k + 2rank([U f -V f ]) -2k = 2rank([U f -V f ]). (5)
In the intermediate calculations we used the fact that for the subspaces of dimension k the rank of the leading elements matrix equals k. Note, that in this case, the final expression for the subspace distance between U and V corresponds exactly to the doubled rank-metric distance between their free elements matrices U f and V f . Now consider a case when the multi-indices U I and V I are not equal. In this case the number of linearly independent columns in the matrix U V is not less than the number of nonzero elements in the vector U v ∨ V v . Therefore,

d sub (U, V) ≥ 2(U v ∨ V v ) -2k = 2(2k -(U v ∧ V v )) -2k = = 2k -2(U v ∧ V v ) = (U v ⊕ V v ) = d ham (U v ; V v ), (6)
where d ham is the Hamming distance between the binary vector-indices U v and V v , corresponding to the subspaces U and V respectively. Thus, for the subspaces within the same multi-index, the problem of building the code with the minimal subspace distance d sub reduces to the construction of a rank-metric code with the minimal distance d rank = d sub /2. For subspaces with different multi-indices, the Grassmannian distance is not less than the Hamming distance between the corresponding vector-indices. Now the task of building subspace codes can be decomposed into two subtasks. First, we need to build a binary code of vector-indices with a minimal Hamming distance d ham = d sub . Then, for subspaces within the same vector-index, we need to build a rank-metric code with the minimal distance d rank = d sub /2, using the free elements of the subspace generating matrix.

Codewords within the same multi-index are called the code component. A subspace code, that contains codewords from more than one code components, is called the multicomponent subspace code.

Constructions of the subspace codes

Historically, the first construction of the subspace codes for random network coding is the Silva-Koetter-Kshishang code (SKK-code) [START_REF] Silva | A Rank-Metric Approach to Error Control in Random Network Coding[END_REF]. Codewords of this code are subspaces, for which the generating matrices in reduced row echelon form have the following representation:

U = I k U f , (7)
where I k is the square identity matrix of order k and the submatrix of the free elements U f is the k × (n -k) rank code matrix over the field GF (q). Equation 8illustrates the form of SKK-code generating matrices for n = 9 and k = 3. Let d rank be the minimal distance of the rank subcode. Then the minimal subspace distance of the SKK-code is equal to d sub = 2d rank . This code construction is often referred to as a lifting construction of the rank-metric code. Note that the SKK-code has only one code component, so it is not the multicomponent code.

U =   1 0 0 * * * * * * 0 1 0 * * * * * * 0 0 1 * * * * * *   . (8)
Gabidulin-Bossert codes with zero prefix [START_REF] Gabidulin | Codes for Network Coding // IEEE Intern[END_REF] have a multicomponent structure. The first component is an SKK-code with the k × (n -k) rank code submatrix. The second component has an all-zero matrix as a prefix of the whole code matrix. The number of rows in this all-zero matrix is equal to k, while the number of columns is equal to δ = d sub /2. The identity matrix of order k follows the zero prefix, and the leftmost positions in the network code matrix are occupied by k × (n -k -δ) rank code matrix. The third code component contains two all-zero matrices as a prefix, and so on for the remaining components.

The number of components in the Gabidulin-Bossert code depends on the code length. The last component contains only the zero prefix and the identity matrix when (n -k) is divisible by δ. Equation 9 represents 3 components of the Gabidulin-Bossert code for n = 9, k = 3 and d sub = 6.

U 1 =   1 0 0 * * * * * * 0 1 0 * * * * * * 0 0 1 * * * * * *   , U 2 =   0 0 0 1 0 0 * * * 0 0 0 0 1 0 * * * 0 0 0 0 0 1 * * *   , U 3 =   0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1   . (9)
In the works [START_REF] Etzion | Error-Correcting Codes in Projective Spaces via Rank-Metric Codes and Ferrers Diagrams[END_REF][START_REF] Etzion | Large Constant Dimension Codes and Lexicodes // Advances in Mathematics of Communications[END_REF] Etzion and Silberstein introduced a greedy lexicographic search of the network code vector-indices among the set of all binary vectors with the length n and Hamming weight k. Their approach gives considerable freedom to choose parameters of the network code, and avoids the use of complex combinatorial circuits. However, this approach does not guarantee that all subcodes in the multicomponent construction are linear rank codes and therefore the decoding algorithm may be nontrivial.

There is another method to construct multicomponent codes. It uses incomplete balanced block designs [START_REF] Hall | Combinatorial Theory[END_REF]. These block designs define multi-indices which in turn specify the location of the columns with the leading elements in the network code matrix. Each multi-index corresponds to one code component. The first code component is an SKK-code and has the greatest cardinality among all the other components. Free elements of the code matrix are used for building rank codes with restrictions [START_REF] Gabidulin | Rank subcodes in multicomponent network coding[END_REF] as subcodes.

This paper is concerned with a combined approach which takes advantage of the two previously described methods. It uses the greedy search of the network code components and linear rank codes with restrictions as subcodes. The remaining sections are devoted to the algorithm of the new multicomponent code construction and its decoding for a network channel with random linear transformations and packet errors.

Rank-metric subcodes

Before describing the new subspace code construction algorithm, we want to comment on the construction of the rank-metric subcodes we will need. For SKKcodes and Gabidulin-Bossert codes, each matrix of the free elements includes a rectangular submatrix that consists only of the free elements (see equation 8 and the first two matrices from equation 9). In this case, one can use these free elements to construct a conventional rank-metric code which is described in detail in [START_REF] Gabidulin | Theory of Codes with Maximum Rank Distance[END_REF].

However, in the case where the columns containing leading elements in the subspace generating matrix are not consecutive, there are some restrictions on the free elements matrix. For example, the generating matrix from equation 1 has the following free elements matrix:

U f =       0 * * * * * * 0 * * * * * * 0 0 0 0 * * * 0 0 0 0 0 0 0 0 0 0 0 0 0 0       . ( 10
)
Zero elements in the free elements matrix are a result of the Gaussian elimination procedure, and they can not be used as a rank-metric code symbols. Therefore, we need to construct a rank-metric code with restrictions, which means that some of its symbols will be zeros for any input consequence. To solve this problem, we suggest using a systematic form of the rank-metric code, which implies that the input consequence is converted to some of the code symbols without changes. These symbols are called informational and all the restrictions will be imposed on them.

Our task is to construct a rank-metric code with the minimal distance d rank = 3 using the free elements matrix from equation 10. Gabidulin construction of the rank-metric code attains the Singleton bound, so d rank = n rank -k rank + 1, where n rank is a total number of the rank-metric code symbols, and k rank is the number of its informational symbols. Note that rank-metric code symbols are vectors over the base field K q , and we can use both horizontal and vertical representation of its expansion in the basis.

Let the vertical representation of rank-metric code symbols be used. Since we can place restrictions only on the informational symbols of the rank-metric code, n rank -k rank code symbols should not have any restrictions. In our case, it means that we have to find n rank -k rank = d rank -1 = 2 columns with at least N free elements each, where N determines the size of the rank-metric code. Our goal is to build the code with the biggest cardinality, so the value of N should be the maximum possible. The number of the informational symbols in the rank-metric code will be equal to N -(n rank -k rank ).

In our case for the free elements matrix from equation 10, we can find d rank -1 = 2 columns with exactly three free elements. It means than N = 3 and the number of information symbols is equal to N -2 = 1. Again, in order to build the rank-metric code with the biggest cardinality, we want informational symbols to be the vectors with maximum possible length. This leads us to construct the following code, using the free elements matrix from equation 10:

U f =      
0 * * * i 11 c 11 c 21 0 * * * i 12 c 12 c 22 0 0 0 0 i 13 c 13 c 23 0 0 0 0 0 0 0 0 0 0 0 0 0 0

      . ( 11
)
This code contains one informational symbol, i 1 = i 11 α 0 + i 12 α 1 + i 13 α 2 , and two code symbols, c 1 = c 11 α 0 + c 12 α 1 + c 13 α 2 , and, c 2 = c 21 α 0 + c 22 α 1 + c 23 α 2 , where α is the primitive element of the field K N q . The cardinality of this code is equal to the number of components of the informational symbols vectors. In our case, it means that the rank-metric subcode cardinality is equal to C v = q 3 . Note that, after the rank-metric subcode construction, we still have six free elements in the matrix U f . In our code construction, these free elements can not increase the rank-metric code cardinality, so their values may be chosen arbitrarily. Now, let the horizontal representation of the rank-metric code symbols be used for the same free elements matrix from equation 10. In this case, we can find d rank -1 = 2 rows with exactly six free elements. It means than N = 6 and the number of information symbols is equal to N -2 = 4. But, there is only one row with the free elements remaining. It means that we have to use three all-zero informational symbols, and only one informational symbol which depends on the input consequence. So the code construction will be the following:

U f =      
0 c 21 c 22 c 23 c 24 c 25 c 26 0 c 11 c 12 c 13 c 14 c 15 c 16 0 0 0 0 i 44 i 45 i 46 0 0 0 0 0 0 0 0 0 0 0 0 0 0

      . ( 12
)
This code contains four informational symbols (three of which are all-zero), i 1 = 0, i 2 = 0, i 3 = 0, i 4 = i 44 α 3 + i 45 α 4 + i 46 5 , and two code symbols,

c 1 = N i=1 c 1i α i-1 and c 2 = N i=1 c 2i α i-1
. The cardinality of this code, as in the vertical representation case, is equal to C h = q 3 , because we again have exactly three free elements in the informational vector positions. However, in some cases it may happen that the cardinalities of the vertical and horizontal representations of the subspace code are not equal. Then, one should chose the representation with the biggest cardinality and the resulting cardinality of the network code component will be equal to

C = max{C v ; C h }.
If, in the process of the rank-metric code construction, we find that there are no free elements in the informational vector positions, then the network code component cardinality will be equal to C = q 0 = 1. This means that this code component will have no subcode. An example of such a code component is the component with the generating matrix U 3 from equation 9.

New multicomponent code construction

Now, knowing how to calculate the cardinality of the rank-metric subcode for any network code component, we are ready to introduce the following greedy algorithm of the code construction.

For the set of all binary vectors-indices of the length n and Hamming weight k, the cardinality of the corresponding rank subcodes is defined. Lexicographically the first vector-index corresponds to the SKK-code, and it will be used as the first network code component, since the SKK-code will always have the biggest cardinality among all the components [START_REF] Gabidulin | Rank subcodes in multicomponent network coding[END_REF].

Then, the greedy search starts for the code component with the biggest cardinality among the remaining components. If its subspace distance to all already added to the code subspaces is not less than d sub , then it is included into the code, and so on. The greedy search ends when there are no subspaces left with the desired subspace distance.

In the case where the intermediate stage of the greedy search algorithm yields more than one code component with the same cardinality, we choose the component with the lexicographically first vector-index. This heuristic is based on an assumption that, with this choice, the cardinality of the remaining components will be greater.

Consider an example of the new construction for the code with the following parameters: n = 7, k = 3 and d sub = 4. All binary vector-indices of the length 6 Decoding for channel with errors and erasures

In random network coding the subspaces are transmitted through the channel by means of their generating matrices. For this purpose, the source of the message sequentially transmits all k rows of the k × n generating matrix, X, that corresponds to some subspace.

Each of the intermediate nodes in the network accumulates all the received rows of the matrix X. Then, the random linear combinations of the rows are transmitted at the first opportunity. In the case when some nodes are under the control of the attacker, these nodes can also distort received messages or add new messages that are neither rows of the matrix X nor their linear combinations.

This channel model can be described by the following equation:

Y = AX + Z, (15)
where the m × k matrix A specifies the random linear transformations of the matrix X, the m × n matrix Z corresponds to the attacker intervention and the m × n matrix Y is the message received by the destination node. The decoding of the received message is possible when d(X; Y ) = d(X; AX + Z) < d sub /2, where d sub is the subspace code distance. It was shown in [START_REF] Silva | A Rank-Metric Approach to Error Control in Random Network Coding[END_REF] that this condition is satisfied when the following restrictions on the matrices A and Z hold:

k -rank(A) + 2rank(Z) < d sub /2. (16)
As well as the code construction algorithm, the decoding algorithm consists of two steps. First, we have to recover the code component of the transmitted subspace. For this purpose we apply the Gaussian elimination procedure to the received matrix Y through multiplication by a nonsingular matrix S: Y = SY = SAX + SZ. Note that the matrix Y corresponds to the same subspace as the received matrix Y . Due to the fact that the matrix S is nonsingular, the decoding condition remains in force: k -rank(SA)+2rank(SZ) = k -rank(A)+2rank(Z) < d sub /2.

Since the matrix Y is in the reduced row echelon form, we can determine its vector-index v Y . From equation 6 we know that d ham (v Y ; v X ) ≤ d(X; Y ) < d sub /2. Together with the subspace code construction method, this condition provides that there is only one code component that has the smallest Hamming distance to the v Y . So, we can find this code component, which corresponds to the transmitted matrix X. The following table represents the simulation results which confirm that for k -rank(A) + 2rank(Z) < d sub /2 the transmitted code component can be recovered correctly in this manner: After the recovery of the code component we have to decode its rank-metric subcode. To achieve this purpose, we suggest making a rearrangement of the leading elements columns in the matrix Y , by moving them in the first k columns, as in the SKK-code. Since the code component has already been recovered, this rearrangement does not affect the decoding conditions. Then, we apply to the resulting matrix exactly the same decoding technique as described in [START_REF] Gabidulin | Rank subcodes in multicomponent network coding[END_REF] for the SKK-code.

Conclusion

We have proposed a new method of multicomponent network code construction, which has no limits on code parameters and allows decoding of channel errors and erasures by means of standard algorithms. In some cases, it allows us to achieve a higher code cardinality than analogous methods.

For the code construction, we use the greedy search algorithm which may seem computationally expensive. But the exhaustive search is required only during the code construction stage, and does not demand additional resources in the process of messages transmission.

An open problem is to effectively find the vector-index which has the smallest Hamming distance to the vector-index of the received matrix. However, we believe that the number of code components in practical use will be quite small, and, thus, the brute force search is not the worst option.

Table 2 .

 2 Error probability in the code component recovery for n = 15, k = 5, d sub = 8. k -rank(A) + 2rank(Z) 0

n = 7 and Hamming weight k 3 are listed in equation 13 in lexicographic order: {1110000, 1101000, 1100100, 1100010, 1100001, 1011000, 1010100, 1010010, 1010001, 1001100, 1001010, 1001001, 1000110, 1000101, 1000011, 0111000, 0110100, 0110010, 0110001, 0101100, 0101010, 0101001, 0100110, 0100101, 0100011, 0011100, 0011010, 0011001, 0010110, 0010101, 0010011, 0001110, 0001101, 0001011, 0000111}.

(13)

The cardinalities of the corresponding rank-metric subcodes for each vectorindex are listed in equation 14: {q 8 , q 7 , q 6 , q 5 , q 4 , q 6 , q 5 , q 4 , q 3 , q 4 , q 3 , q 2 , q 2 , q 1 , q 0 , q 6 , q 5 , q 4 , q 3 , q 4 , q 3 , q 2 , q 2 , q 1 , q 0 , q 3 , q 2 , q 2 , q 1 , q 1 , q 0 , q 0 , q 0 , q 0 , q 0 }.

(14)

We chose the SKK-code with the vector-index v 1 = (1110000) and cardinality C 1 = q 8 as the first code component. The next (in descending order of cardinality) component has the vector-index v 2 = (1101000). But its subspace distance to the first code component is equal to 2, which is less than the desired d ham = d sub = 4, so we can not add it to the code. The first component in the descending cardinality list with the appropriate subspace distance has the vector-index v 10 = (1001100) and cardinality C 10 = q 4 . It is added to the code and the greedy search continues.

Upon completion of the greedy search we obtain the network code of 7 components with the following muli-indices: I 1 = {1, 2, 3}, I 2 = {1, 4, 5}, I 3 = {2, 4, 6}, I 4 = {3, 4, 7}, I 5 = {2, 5, 7}, I 6 = {3, 5, 6}, I 7 = {1, 6, 7}. Its cardinality is equal to M = q 8 + q 4 + q 3 + q 2 + q + q + 1.

This code is equivalent to the code built in [START_REF] Gabidulin | Rank subcodes in multicomponent network coding[END_REF] for the same parameters using block designs. But, in some cases, the new code construction allows to obtain a larger cardinality. To illustrate this, we use the concept of the code efficiencythe ratio between its actual value and the theoretical bound from equation 4. The following table shows the values of efficiency for the SKK-code -η SKK , the Gabidulin-Bossert code -η GB , and the new multicomponent code construction -η new , for a fixed set of the code parameters. 8 ηSKK 0,875 0,82 0,794 0,782 0,777 0,774 ηGB 1 0,823 0,796 0,782 0,777 0,774 ηnew 1 0,835 0,798 0,785 0,778 0,775