his Empire, the only territory he actually controlled. So he decided to strengthen its defences. First, he issued a law, the Novella Maioriani 8 known as De reddito iure armorum ("On the Return of the Right to Bear Arms"), concerning the personal right to bear arms; in 440, Valentinian III had already promulgated a law with the same name, Novella Valentiniani 9, after another attack of the Vandals. It is probably to this time that another law is to be dated, the Novella Maioriani 12 known as De aurigis et seditiosis ("Concerning Charioteers and Seditious Persons"), to quell the disorders that sprang up during the chariot races. Both these laws are now lost. He then strengthened the army, recruiting a large number of barbarian mercenaries, including Gepids, Ostrogoths, Rugii, Burgundians, Huns, Bastarnae, Suebi, Scythians and Alans. Finally, he rebuilt two fleets, probably those of Miseno and Ravenna, since the Vandals had a strong navy: Reconquest of Gaul After consolidating his position in Italy, Majorian concentrated on the recovery of Gaul. When news of the deposition of the Gallo-Roman emperor Avitus arrived in Gaul, the province refused to recognize Majorian as his successor. An important clue to this is an inscription found in Lugdunum (modern Lyons) and dating to 458: according to Roman custom, the inscriptions were dated reporting the name of the consuls in office, who that year were Leo I and Majorian. This inscription, instead, records only the name of Eastern Emperor, showing that Majorian was not recognized as lawful Emperor. Another clue is the fact that, at the death of Avitus, the citizens of Lugdunum had allowed the Burgundians of king Gondioc to occupy the city, and that they sent an envoy to Leo, and not to Majorian, to ask for a reduction of taxation. Finally, there is a record of a failed usurpation in Gaul, around this time. In late 458, Majorian entered Gaul, with an army strengthened by barbarian units. The Emperor personally led the army, leaving Ricimer in Italy and choosing Aegidius and the magister militiae Nepotianus as collaborators. The imperial army defeated the Visigoths under king Theodoric II at the Battle of Arelate, forcing the Visigoths to abandon Septimania and withdraw west to Aquitania. The Roman victory was decisive: under the new treaty the Visigoths had to relinquish their vast conquests in Hispania and return to federate status. Majorian chose his trusted general Aegidius