Ewan Dunbar

Generative grammar, neural networks, and the implementational mapping problem: Response to Pater

On the same list that ranked Syntactic Structures as the number one most influential twentieth-century work in cognitive science, the number two work cited is David Marr's Vision [START_REF] Marr | Vision: A computational investigation into the human representation and processing of visual information[END_REF]. Marr proposed that the only way to achieve a complete understanding of complex information processing systems like those found in the brain is to simultaneously analyze the system at three different levels of analysis: a computational level, where one formally defines the problem that the system is solving, specifying which inputs must map to which outputs; as well as an algorithmicrepresentational level, where one spells out a method for arriving at an output, given a particular input-a formal hypothesis about how the system encodes information, and how it manipulates it; spelled out at an implementational level, which details in what sense the physical system in question can actually be seen as carrying out the proposed algorithm. Generative grammar standardly proposes to analyse language cognition at the first two levels, leaving the problem of how such a system would actually be implemented in the brain open-leaving open, thus, the nature of the link between the algorithmic-representational theory and the physical implementation. Specifying and evaluting any such link is a difficult problem in itself-call it the implementational mapping problem.

Pater's proposal for closer interdisciplinary integration between generative grammar and connectionist research will immediately run up against this problem too. Neural network models are not brains, or even brain models, but they are complex systems whose behaviour cannot by understood without some amount of analysis. There is an increasing recognition that we lack good methods for understanding how a given neural network model works-for giving a highlevel characterization of how the system encodes and manipulates information-and a recognition that, for several reasons, this is an untenable state of affairs. For the time being, this opacity poses serious limits on what we might hope to achieve in a closer integration between connectionist and formal linguistic theories. While we might be able to tell whether and how well a network model is able to learn some linguistic phenomenon, we currently are very limited in our tools for understanding what a given network has learned.

Feedforward neural networks can in principle approximate any function with arbitrary precision. Thus, in principle, they can implement any grammar we can imagine. Clearly, this has the potential to make neural networks extremely useful tools for modelling learning in generative grammar. But their opacity prevents us from arriving at satisfactory answers to basic questions. Has the network arrived at a solution which is (a notational variant of) a grammar made possible under a specific linguistic theory T? Has it arrived at an approximation to such a grammar? Has it arrived at some alternate, unforeseen solution, possible under T, or does its solution fall outside the bounds of T? Can all possible parameter settings learnable in a given network be seen as licit grammars in T, or some approximations to such a grammar? Conversely, can all licit grammars in T be represented or approximated with a given network architecture? In order for the network to learn solutions in the scope of T, does it require special evidence, inaccessible to the child? Or are such grammars always learnable from realistic data? Before we can use neural networks to help us answer these fundamental questions about learnability of grammars, we need to seriously address the problem of how to construct and evaluate a mapping between a grammar defined in a linguistic formalism, on the one hand, and a neural network model, on the other, which may (or may not) encode linguistic knowledge in exactly the way predicted by that grammar.

The implementational mapping problem

Before understanding how the implementational mapping problem is relevant to neural networks, it is useful to look in more detail at Marr's methodological framework, to understand the nature of the problem. Consider the obvious fact that, when a human brain is cut open, trees do not come fanning out. Does this mean that syntax is wrong? No. Even if we had in hand detailed physical state of every neuron in the brain, we would need to do work to understand what they were doing, in the same way that we do now-by proposing and comparing theories. But to do so we would need to have a precise notion what it would mean for neurons to "do something" in a particular way. Assuming that some model of a system correctly describes its inputs and outputs (what the system does), how can we determine whether the description at Marr's algorithmic-representational level (how it does it) is in really line with the physical object?

Marr's levels of analysis are easily understood using his example of addition of natural numbers. Addition is a function that applies to two natural numbers, and results in some other natural number. There are various kinds of physical systems of which it can be correctly said that they "do addition." A computational level description of such a system would be any complete, accurate description of the behaviour of the two-place function add(•, •)-what kinds of inputs does it take, and what is the relation between its inputs and its outputs? In other words, what does it do? There are various sets of mathematical axioms for arithmetic, some of which are logically equivalent to one another, and others of which define interesting weaker or stronger variants of familiar operations. What they all have in common is that they are sets of formal constraints: the necessary and sufficient conditions for a function add(•, •) to be reasonably called "addition," along with precisions about what rules its inputs and outputs need to follow (in order to be thought of as "numbers"). For example, one such set of axioms, due to Giuseppe Peano, can be given as follows [START_REF] Mendelson | Introduction to Mathematical Logic[END_REF]:

Axioms about numbers 1. The set of numbers (N) is a set that contains an element called 0 (among other things) 2. There is a unary function called successor(•) such that a. For all x ∈ N, successor(x) ∈ N b. There is no element xof N such that successor(x) = 0 c. If successor(x) = successor(y) then x = y, and conversely 3. If some predicate p is true of 0, and, whenever p(x) is true, then p(successor(x)) is also true, then pis true for all elements of N Axioms properly about addition 4. There is a binary function called add(x, y) such that a.For all x ∈ N, add(x, 0) = x b.For all x, y ∈ N, add(x, successor(y)) = successor(add(x, y))

From these axioms it is easy to prove useful things like, For all x, add(x, successor(0)) = successor(x), and that, For all x, add(0, x) = x, and, from these, that add(x, y) = add(y, x)-and all other familiar facts about addition. The axioms precisely state what constraints the inputs must respect, and specify exactly what the output of any addition must be, in relation to its inputs.

A computational-level theory of addition is quite different from a physical implementation of addition. This might take the form of a person using an abacus, or doing arithmetic with a pencil and paper, or a spreadsheet taking inputs with a keyboard and giving outputs on a computer monitor. Each of these physical systems include many particles, human brains and fingers, and possibly transistors, beads, or graphite-all of which are rather complicated systems in themselves, all told-but, provided they do nothing other than addition, and do so correctly, then the computationallevel theory of addition is an accurate theory of all of their behaviour. The fact that a physical system is doing addition might be intuitively obvious post hoc, after the implementational mapping problem has been solved-if you know what addition is, and you have been to school in the West, then you can probably quickly tell when a sequence of scribbles on paper "is" an addition computation. But this background is useful exactly because it tells you how to map numbers onto marks on paper, and allows you to recognize the individual steps of a known algorithm for adding them. Without this background, the fact that the computational theory of addition is a correct model of this physical system is not actually "obvious" at all. To convince yourself of this, add some numbers on paper and ask a sample of four-year-olds to explain to you what you are doing. Four-year-olds' inability to give any useful explanation is partly due to their lack of understanding of addition, and partly to a general difficulty in providing useful explanations of things, but also in part due to any knowledge of what addition could look like. It does not take much more effort to imagine systems implementing arithmetic which would be completely opaque even to an adult with a solid knowledge of how addition works. 1 For example, consider a person verbally describing the steps of adding two numbers in a foreign language; or an undeciphered clay tablet showing calculations (perhaps using letters of the alphabet as numbers); or a machine that takes two sounds as input, and, if both are pure tones, outputs a new pure tone with a frequency equal to the sum of the two. Any of these, encountered without any knowledge of what they "really" were, would, at first, be inscrutable.

Marr presents a compelling case that to fully understand a system is not only to find a consistent computationallevel theory of it, but also to arrive at an understandable, low-level description of the basic physical elements of the implementation-and to be able to link the one to the other. Critical to making this link is Marr's second level of description, algorithmic-representational level. Going beyond describing what a system does, an algorithmicrepresentational description describes how it does it-without going into any detail that's tied to a specific physical im-plementation. Coming back to addition: how are numbers represented? Several practical possibilities might be decimal numbers (successor(6) = 7), binary numbers (successor(110) = 111), or unary numbers (successor(||||||) = |||||||), but these are not the only possibilities (for example, successor(VI) = VII). Any one of these systems could be implemented in a variety of physical systems. Unary numbers are familiar because they are so easy to implement: with fingers, sticks, or coins. Roman numerals are normally only encountered in written form-but Roman numerals can be written in upper-case or lower-case, transmitted in Morse code, written using a symbol font-and, of course, stored in a computer as sequences of binary digits. All of these are different physical implementations.

Of course, to properly assess whether a representational system "is" or "is not" a correct theory of a physical system, one must, again, spell out that representational system in some formal detail. To describe a unary encoding, for example, one might simply say that there is a basic element which we write |; that each number in N is encoded as a unique sequence consisting only of some number of |'s; and that longer strings always represent larger numbers and conversely. To spell all this out, we would in turn rely on explicit definitions of "sequence" and of "longer," both of which could be mapped to the physical system in some coherent way. A system implementing a unary encoding would not need to contain any actual physical lines written |, but it would need to be coherent with these axioms. A system implementing unary numbers would be different decimal numbers: in the first, it would be true that the physical equivalent of "longer" representations were necessarily larger numbers-but not in the second.

Note that the theory of natural numbers formalized above in axioms (1-3) makes reference to a function called successor(•). This function exists as part of a mathematical definition, but it does not need to have any physical reality: there does not need to be a basic operation "add one" in order for a system to be correctly described by these axioms. A system implementing addition does not even need to have a single physical operation corresponding to the function add(•, •). However, it does need to be capable of doing more than just representing numbers: it needs to be doing addition in some way-using some algorithm. There are many algorithms for doing addition, and the choice of algorithm and the choice of representation are not independent. The familiar column-wise addition with carrying that most children in the West learn for doing addition on paper will work with decimal, binary, or even unary representations; it will not work with Roman numerals. And, although it will work with unary representations, it is not the algorithm one typically uses. The usual method is simple concatenation: |||| + ||| = |||||||. But, much to the frustration of young children everywhere, concatenation does not work as a method for adding numbers in decimal representation: 4 + 3 does not equal 43. An algorithm is a set of implementation-neutral steps for manipulating representations which yields results consistent with the computational-level description of the system. For the algorithmic-representational level description of a system to be correct, there needs to be some consistent mapping between, on the one hand, the physical elements of the system and the changes they undergo in time, and, on the other hand, the basic representational elements and computational steps given by some formally explicit description of an algorithm and a representational system.

The problem of proving that an algorithm does what it is supposed to do at the computational level is a problem familiar to computer science students. The implementational mapping problem, on the other hand, is the problem of defining, and empirically evaluating, some mapping between an algorithmic-representational level description, and a physical system. In other words, it is the problem of knowing what to look for. This problem is hard. It is made even harder by the fact that Marr's picture is idealized. Systems do not really have only three useful levels of description. A modern computer, for example, is best understood using a large hierarchy of descriptions. I can write Eratosthenes' algorithm for finding prime numbers on a computer. Before being executed, the algorithm will be translated-using another computer program, the compiler-into a sequence of steps rather different from the ones I specified. The compiler will both add steps (when translating my instructions into sequences of instructions understandable by the processor) and remove steps (when it does predictable optimizations). Similarly, I can write an algorithm that simulates doing addition in the way that I learned in school: by representing numbers as strings made up of the characters 0, . . . , 9, identifying the "columns," lining them up, adding by column, and carrying when necessary. But each of these strings representing numbers, and each of its component characters, will be stored in the computer's physical memory as binary numbers, using a specific mapping between characters and numbers; translating to and from this representational format represents a system in and of itself. Thus, while it might be correct to say that my program represented numbers in a decimal format, this is only correct if I see my computer memory, as seen from the point of view of my programming language-a set of "objects" corresponding to strings and characters-as the basic "physical" elements of the system-which of course, they are not really. For cognitive science, this suggests that drilling all the way down to the physical implementation level-the human brain-may ultimately require having various intermediate theories of "middle-level" representation. However, even if things were simple in the ideal, the implementational mapping problem would nevertheless be extremely difficult, deserving of careful attention.

The implementational mapping problem in generative grammar

Although my focus here is not on the brain, generative linguists will generally have thought, to one degree or another, about the implementational mapping problem, because of questions about how their theories might be implemented in the brain-the standard "Chomskyan" approach to treat grammars as abstract (not implementation-level) theories of real human language cognition invites these kinds of reflections.

As a point of clarification, however, it is worth pointing out that Marr's division of methodological labour into three levels of analysis is one that does not neatly line up with the way generative grammars are usually given a cognitive interpretation. The standard education in linguistics always includes some insistence on the idea that the series of steps carried out on paper to derive a sentence, or a phonological surface form, are not meant as a theory of the series of steps carried out in the mind. In other words, no theory of the algorithm is implied by the theory of the grammar. Yet, typically, the student is told, the theory of the representation (the trees, feature bundles, and so on) is supposed to be cognitively intepreted; the derivational steps are merely to be intepreted as a means of stating which representations are licit structural descriptions, not to be interpreted as bearing a direct relation with any computational "steps" in the brain.

This specific interpretation of formalism in generative grammar is not logically necessary, nor is it by any means universal. [START_REF] Chomsky | The Minimalist Program[END_REF] best states this point of view when, in his criteria for descriptive adequacy of grammars characterizing linguistic competence, he includes the criterion that the grammars yield psychologically correct structural descriptions (representations)-not merely the the (computational) criterion that they pick out all and only the grammatical sentences of the language. He does not, however, require that a grammar give us any notion at all of how parsing is done on-line (an algorithm: see pp. 17-18). Some researchers, however, have interpreted the derivational steps one could go through using a phrase-structure grammar in to derive a sentence as making empirically testable algorithmic assertions about how structure is actually built. For example, [START_REF] Miller | Finitary models of language users[END_REF] proposed that psycholinguistic criteria for evaluating a syntactic grammar could be developed, under the assumption of a "transparent" parsing, with a list of rewrite rules stored explicitly in memory, and parses by executing steps corresponding to these rules. See [START_REF] Berwick | The Grammatical Basis of Linguistic Performance: Language Use and Language Acquisition[END_REF] and [START_REF] Phillips | Order and structure[END_REF] for further discussion. On the other hand, some authors have suggested that the only reasonable place to situate formal grammars is at the purely computational level, specifying the function computed by the mind, and nothing more [START_REF] Matthews | Psychological reality of grammars[END_REF]. Under this view, two different theories that predict the same set of possible words or sentences would be equivalent. All the rules, representations, and derivations would be purely instrumental. This is not a standard view however. Derivations are typically not intended as cognitively real steps, but the representations they yield (including, presumably, intermediate steps in serial derivations) are thought to have empirical reality (apart from their indirect consquence that they help the grammar to pick out the right set of grammatical strings).

Few linguists would suggest that opening the brain and looking around would be sufficient to come to a satisfactory solution to the implementational mapping problem with respect to a given linguistic theory, and few would assume that the problem of knowing what to look for has some simple solution from neuroscience (it does not). The same holds if we wish to exploit neural networks to model learning of grammatical knowledge: we must somehow deal with the problem of knowing how to interpret what is learned as a grammar of some kind.

The implementational mapping problem in connectionism

Given the enthusiasm about the analogues between neural networks an brains in the introductory chapters of the original connectionist manifesto [START_REF] Rumelhart | Parallel Distributed Processing: Explorations in the Microstructure of Cognition[END_REF], one could be forgiven for thinking that, in these early days, the mere existence of a neural-network model of some cognitive task might have been interpreted as having solved the scientific problem of understanding the relevant human brain system, even if no actual brain were ever compared with the model. Great enthusiasm about standard neural networks as veridical brain models is no longer common. Despite the fact that they have their origins in brain models, and despite the fact that they are typically made up of many binary response functions-which can be said to "spike," just like many neurons do-they are today largely seen as powerful families of statistical models with many parameters, rather than attempts at faithful models of physical brains. Typical modern feed-forward neural networks differ in too many ways from real brains to be able to allow us to automatically draw the inference that there is, or even could plausibly be, something comparable going on in the brain system responsible for some aspect of cognition, just because we are able to construct a neural network model.

Neural networks are not brains, but they are complicated and opaque systems. The sheer number of parameters and their sometimes very indirect and complicated relations with the inputs and outputs of the task on which they are trained means that any given neural network, if it is to be truly understood, requires an analysis as a complex system in and of itself. The Marrian framework can provide an approach to doing this: if the parameters of the system are seen as the "physical" reality of the system, then a correct algorithmic-representational description of the system would allow researchers to correctly reason about the information coded in the system and how it passes through various layers of the network. Such a description must be deduced, like that of any other opaque complex system.

The state of the art in such analysis of networks is somewhat limited; this is unfortunate, because among the motivations for wanting to construct theories of what networks are doing are some practical and pressing ones. New regulations in the European Union require that automated decisions taken on the basis of user-provided information be explained to the end user [START_REF] Goodman | European Union regulations on algorithmic decision-making and a "right to explanation[END_REF]. This is not currently possible for any satisfying sense of "explanation"-current attempts are typically limited to telling the user that a decision (to show an advertisement, for example) was taken "on the basis of" a laundry list of relevant factors. Reporting which features have the most importance for a given classification in a feed-forward neural network is a well-explored problem [START_REF] Erhan | Visualizing higher-layer features of a deep network[END_REF]Springenberg et al., 2014), but recovering a simple description of the network's "chain of reasoning" is not. And the problem is not merely one for end-users. Neural network models are increasingly used in mission-critical systems where developers and system testers must be able to reason in some way about the network's behaviour in order to ensure that the system is safe. From this perspective, neural networks can be seen as complex, automatically generated computer programs for which no human-readable "source code" is available-for which such source code must be inferred if the system is to be debugged. At present, we are far from having good, general-purpose methods for doing so.

There is another reason, more immediately relevant to a cognitive scientist, to be interested in mapping neural network models to high-level formal "theories" describing their operation. Although standard neural networks are not faithful biological models, it is substantially easier to imagine turning them into serious and realistic brain models than to imagine starting from scratch. There is certainly something brain-like about typical neural networks-they are made up of many binary response functions, and brain systems contain many spiking neurons; there are even plenty of encouraging results using out-of-the-box neural networks to predict real neural activation, giving at least suggestive hope that the gap in the mechanisms could perhaps be bridged (see [START_REF] Kietzmann | Deep neural networks in computational neuroscience[END_REF]. Thus, an effort to map a neural network's internal representations to those of some formal theory-and the consequent step of comparing different hypotheses about how to best characterize a network's representations-could be a first step towards developing characterizations of what various theoretical proposals might look like if implemented neurally-helping us to then know what to look for. Whether or not this proves to be true, I suspect strongly that the simple project of engaging with the implementational mapping problem will prove useful for the project of understanding real brains-even if the complex systems we initially analyse are completely artificial-in the same way that developing grammatical formalisms for artificial formal languages was a crucial step in the development of linguistic theories which continues to be a fruitful source of mathematical insight about human languages today.

Determining whether, or to what degree, an algorithmic-representational theory really reflects how a neural network is operating can be seen as a problem of fitting a model to data-except that, in this case, the "data" consists of internal information about how a network treats specifically selected inputs, and the model provides some set of expectations about how it should treat this inputs. Model fitting is best seen as a comparative exercise of trying to select the comparatively best model for a given set of data. We can think of two fundamental problems, therefore, in the assessment of how a neural network should be interpreted: can a given network be seen as implementing, or approximating, the algorithmic-representational theory X, or is network Y a better model? Is a given algorithmic-representational theory implemented or approximated by network M, or is network N closer to the predictions of the theory?

While this idea of "decoding" the action of connectionist networks in terms of some interpretable "model" of their behaviour is quite old, the theoretical tools for doing so are still far from being well-developed enough to be commonly applied to real networks. The paper by [START_REF] Pinker | On language and connectionism: Analysis of a parallel distributed processing model of language acquisition[END_REF], responding to the connectionist past-tense inflector of Rumelhart and McClelland (1986a), did not provide any reusable methodological tools for understanding other neural network models; but it did provide a long exegesis of the behaviour of a single network, providing proof that such networks could be "understood," and did not need to remain black boxes. Properly within the realm of neural network research, as discussed above, a number of techniques have been developed for assessing the relative importance of the different input features in determining the output; relatedly, starting in the early 1990s, a number of "rule extractor" techniques were developed that could be used to turn the parameters of neural networks into sequences of rules operating on the (possibly continuous) input space of the network (sometimes yielding only approximations to the network's behaviour). However, none of these techniques are applicable to the problem of extracting sequences of exact rules from the types of network architectures in common usage today (Taylor and Darrah, 2005;[START_REF] Özbakır | A soft computing-based approach for integrated training and rule extraction from artificial neural networks: Difaconn-miner[END_REF][START_REF] Augasta | Reverse engineering the neural networks for rule extraction in classification problems[END_REF]. Furthermore, none provides useful general tools for addressing the two fundamental problems just presented.

Despite the relative methodological infancy of the field, the problem of decoding neural network information processing has seen a sharp uptick in interest in recent years, probably due in some proportion to the practical need to interpret working systems, but also at least as much (and likely more so) to the "analogy" result of [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF]. The authors demonstrated that the representation of king, learned by a neural network solely on the basis of sequential relations in natural text corpora, stood in the same geometric relation to the representation of queen as man stood to woman, and, more generally, that representations in the system approximated an implicit semantic feature structure. The methodology used to determine this provides a method for assessing, given a specific hypothesized set of binary featural contrasts, whether one network approximates them better than another. The method has been applied, with some variations, to a host of other types of representations since [START_REF] Gladkova | Analogy-based detection of morphological and semantic relations with word embeddings: what works and what doesn't[END_REF][START_REF] Dunbar | Quantitative methods for comparing featural representations[END_REF][START_REF] Linzen | Quantificational features in distributional word representations[END_REF][START_REF] Chaabouni | Learning weakly supervised multimodal phoneme embeddings[END_REF]. The original method has been criticized as giving erroneous results in various cases, and for making narrow and unmotivated assumptions about the form of the mapping between the network's representations and the hypothesized feature system [START_REF] Levy | Linguistic regularities in sparse and explicit word representations[END_REF][START_REF] Linzen | Issues in evaluating semantic spaces using word analogies[END_REF], but it provided both a compelling result and a reminder of a compelling idea-old, but under-sold: there are ways of interpreting neural network representations as respecting the structure of some abstract, and understandable, theory.

Tensor product representations [START_REF] Smolensky | On the proper treatment of connectionism[END_REF] represent a more general framework for stating mapping hypotheses between neural network representations and formal representational theories, which allow for mappings between network weights and complex hierarchical representations. However, up to now, published work in this framework has not directly addressed the two fundamental decoding problems. For example, [START_REF] Palangi | Deep learning of grammatically-interpretable representations through question-answering[END_REF], cited by Pater, presents a network which is specifically trained to be interpretable by imposing a specific mapping to a linguistic representation. A different line of research is represented by the method of [START_REF] Kriegeskorte | Representational similarity analysis-connecting the branches of systems neuroscience[END_REF] for assessing isomorphisms of two representational systems. This method is, in principle, applicable to the implementational mapping problem, but it has almost exclusively been used for comparing neural network representations against equally opaque data from brain imaging (seen as "representations" in a broad sense).

Conclusion

Neural networks are complicated and opaque, and must be analyzed as such. Pater insists on the immediate importance of a research program that goes back to the early days of connectionism [START_REF] Fodor | Connectionism and cognitive architecture: A critical analysis[END_REF]Smolensky, 1988a;[START_REF] Mccloskey | Networks and theories: The place of connectionism in cognitive science[END_REF]: neural networks can and should be seen as implementations of (approximations to) formal theories of linguistic knowledge. This is indeed a promising research direction whose time has come. However, in the spirit of Marr's approach to understanding the brain as a complex system, before an interdisciplinary research program of the kind envisioned by Pater can be made real, a very concrete, broad and well-thought-out set of formal methodologies for posing the question of how well a particular neural network aligns with a linguistic theory, stated at Marr's algorithmic-representational level toolkit, is needed. Without careful reflection on what it would mean for a grammatical hypothesis to be "instantiated" in a neural network, and ways to understand what kind of alternative representations a network model is proposing to us, we will be lost in this endeavour.

The above discussion should not be taken to suggest that there is a general, universal solution to the implementational mapping problem. Take the second fundamental decoding problem, giving relative scores to two different networks to assess which one is a closer approximation to a given representational system. Mikolov et al's "analogy" approach, and related approaches to the problem of assessing coherence of a network with binary feature representations, work by assessing whether minimal feature oppositions, such as those between king and queen, or man and woman (differing minimally in semantic gender), can be captured by doing arithmetic addition and subtraction operations (does kingqueen + man equal woman?). This assumes a very specific type of implementational mapping, wherein the structure of the network's representational space is necessarily one in which addition of the vectors representing two words is the network's equivalent of feature composition. This may be reasonable in specific types of networks-and it may be true-but it may also be inappropriate: a network might "contain" binary semantic features in some different sense, using a structure based on something other than addition. Indeed, we already know that there is no single, universal way of "interpreting" real neurons: gerbils and chickens' neural systems for sound localisation in the horizontal plane in front of the body can be described in the same algorithmic-representational terms-calculating inter-aural time differencesbut this information is coded in neural firing in a fundamentally different way across the two species (see [START_REF] Ashida | Sound localization: Jeffress and beyond[END_REF]. Any attempt to "find" inter-aural time differences in gerbils under the expectation that it should be encoded in the same way as in chickens would lead to a negative result (they are coded using neural firing rate in mammals, but not in birds). This would lead to the false conclusion that the two species' brains perform fundamentally different operations, while, in fact, they perform they same operations in different ways. The problem is not insurmountable, but simply needs to be taken into account: any assessement of the congruence between an opaque (neural network) representation and a high-level formal theory is necessarily and inextricably bundled with the assessment of the validity of the mapping hypothesis.

It should also be pointed out that there are several related lines of research which are important, but which do not represent formal tools for evaluating formalism-network mappings in the way I sketch here. First, as discussed by Pater, violable constraint-based grammar formalisms have their origins in the insight that certain classes of neural networks can be also be formalized as sets of weighted constraints [START_REF] Smolensky | Information processing in dynamical systems: Foundations of harmony theory[END_REF]. The import of this is that the problem of mapping to a neural network has a solution for a specific type of formalism and a very specific type of network architecture; it is not in and of itself an attempt to find ways of analysing other types of networks or other types of formalisms. Second, much recent literature has attempted to build linguistically informed tests assessing whether learned systems form correct linguistic generalizations-for example, the goal of the paper by Linzen et al. (2016a) cited by Pater is to construct a set of grammaticality judgment tests to assess whether networks trained on text form correct generalizations about agreement in English (see also [START_REF] Gulordava | Colorless green recurrent networks dream hierarchically[END_REF] for an updated, and rather different, result). While this paper can be seen as assessing whether the network's knowledge of English is consistent with hierarchically "structure"-dependent generalizations, it does not directly demonstrate the presence of hierarchically structured representations in the network. This kind of careful, linguistically informed extrinsic, or behavioural, evaluation is also critical to the interdisciplinary project proposed by Pater. But it is not the same as the equally critical project of understanding how we can interpret networks using abstract formalisms and, conversely, how we can ground abstract formalisms in neural network implementations. Taylor, B. J. and Darrah, M. A. (2005). Rule extraction as a formal method for the verification and validation of neural networks. In Neural Networks, 2005. IJCNN'05. Proceedings. 2005 IEEE International Joint Conference on, volume 5, pages 2915-2920. IEEE.

By this I don't mean knowledge of a formal set of axioms for addition, but simply an everyday understanding of arithmetic. Knowing a set of explicit rules and regulations for arithmetic would be essential to giving a reproducible and externally verifiable scientific demonstration, but an intuitive understanding addition would presumably be sufficient, in most cases, to recognize when a system was doing arithmetic, in the same way that being able to cite all the rules of baseball in their official format is generally not necessary simply in order to be able recognize when a baseball game is being played or described.


Om Prakash

Shikha Yadav

Habibul Islam

Patrick Solé
email: sole@enst.fr

Self-dual and LCD double circulant codes over a class of non-local rings

Keywords: Double circulant code, LCD code, Self-dual code, Gray map, Quasi-cyclic code Mathematics Subject Classification (2000) 94B05, 94B15, 94B35, 94B60

Let F q be a finite field of order q = p m where p is an odd prime. This paper presents the study of self-dual and LCD double circulant codes over a class of finite commutative non-chain rings R q = F q +uF q +u 2 F q +• • •+u q-1 F q where u q = u. Here, the whole contribution is two-folded. Firstly, we enumerate self-dual and LCD double circulant codes of length 2n over R q , where n is an odd integer. Then by considering a dual-preserving Gray map ϕ, we show that Gray images of such codes are asymptotically good. Secondly, we investigate the algebraic structure of 1-generator quasi-cyclic (QC) codes over R q for q = 3. In that context, we present their generator polynomials along with their minimal generating sets and minimum distance bounds. Here, it is proved that ϕ(C) is an sq-QC code of length nq over F q if C is an s-QC code of length n over R q .

Introduction

Self-dual double circulant codes over finite fields have remained worthy of study for more than three decades [START_REF] Ventou | Self-dual double circulant codes[END_REF]. Recently, their enumeration and asymptotic performance over finite fields have been presented in [START_REF] Alahmadi | On self-dual double circulant codes[END_REF]. However, there is a scope to extend this study over finite commutative rings where -1 is a square. Towards this end, the Chinese Remainder Theorem (CRT) approach, which was introduced in [START_REF] Ling | On the algebraic structure of quasi-cyclic codes I: Finite fields[END_REF] for quasi-cyclic codes, can be employed. On the other hand, a special kind of linear code, namely, linear complementary dual (shortly, LCD), was introduced in 1992 [START_REF] Massey | Linear codes with complementary duals[END_REF]. They have defined LCD codes as linear codes having trivial intersections with their dual. These codes play an important role in preventing side-channel attacks (SCA), fault-injection attacks (FIA) in embarked cryptosystems [START_REF] Carlet | Complementary dual codes for counter-measures to side-channel attacks[END_REF], and in multi-secret sharing schemes [START_REF] Prakash | Constacyclic and Linear Complementary Dual codes over Fq + uFq[END_REF]. These codes are worth studying over different alphabets (finite fields and rings) [START_REF] Islam | Cyclic codes over a non-chain ring Re,q and their application to LCD codes[END_REF][START_REF] Islam | Construction of LCD and new quantum codes from cyclic codes over a finite non-chain ring[END_REF][START_REF] Li | LCD cyclic codes over finite fields[END_REF][START_REF] Liu | LCD codes over finite chain rings[END_REF]. In the last three years, both self-dual and LCD double circulant codes experienced intense attention over finite commutative rings, like Z p 2 (p is prime) in [START_REF] Huang | Double Circulant Self-Dual and LCD Codes Over Z p 2[END_REF], Z 4 in [START_REF] Shi | Double circulant LCD codes over Z 4[END_REF], and Galois rings in [START_REF] Shi | Double circulant self-dual and LCD codes over Galois ring[END_REF]. In 2020, self-dual and LCD double circulant and double negacirculant codes over the non-chain ring F q + uF q , where u 2 = u are studied in [START_REF] Shi | On self-dual and LCD double circulant and double negacirculant codes over Fq + uFq[END_REF]. The enumeration and performance of such codes have explicitly been presented there.Further, these codes are investigated over another non-chain rings F q + vF q + v 2 F q , v 3 = v in [START_REF] Yao | On self-dual and LCD double circulant codes over a non-chain ring[END_REF] and F q [v]/⟨v 2 -1⟩ in [START_REF] Yadav | Enumeration of LCD and Self-dual Double Circulant Codes Over Fq[v]/⟨v 2 -1⟩[END_REF]. Recently, we [START_REF] Yadav | Self-dual and LCD double circulant and double negacirculant codes over Fq + uFq + vFq[END_REF] investigated self-dual and LCD double circulant and double negacirculant codes over F q +uF q +vF q where u 2 = u, v 2 = v, uv = vu = 0. In continuation, here we consider a class of non-chain rings R q = F q + uF q + u 2 F q + • • • + u q-1 F q , u q = u of size q q , where q = p m and p is an odd prime. The ring R q has a special interest and was explored in several studies [START_REF] Goyal | Duadic codes over the ring Fq[u]/⟨u m -u⟩ and their Gray images[END_REF][START_REF] Goyal | Quadratic residue codes over the ring Fp[u]/⟨u m -u⟩ and their Gray images[END_REF]. This paper enumerates both self-dual and LCD double circulant codes over R q . In addition, using a Gray map ϕ which carries self-dual (resp. LCD) codes over R q to self-dual (resp. LCD) codes over F q , we show that the Gray images of such codes constitute an asymptotically good family of codes.

In the second part of the paper, we investigate 1-generator quasi-cyclic (QC) codes over R q for q = 3. It is well known that quasi-cyclic code is one of the most remarkable and studied generalizations of cyclic codes and hence consists of several record-breaking codes [START_REF] Gulliver | Some best rate 1 p and rate p-1 p systematic quasi-cyclic codes[END_REF][START_REF] Gulliver | Twelve good rate (m-r) pm binary quasi-cyclic codes[END_REF]. By using the Chinese Remainder Theorem (CRT) approach, Ling and Solé investigated the algebraic structure of these codes over finite fields [START_REF] Ling | On the algebraic structure of quasi-cyclic codes I: Finite fields[END_REF], and over chain rings [START_REF] Ling | On the algebraic structure of quasi-cyclic codes II: Chain rings[END_REF], respectively. Further, when a quasi-cyclic code is generated by a single element as a module over some auxiliary ring, then it is called a 1-generator quasi-cyclic code. Such codes have been studied in several series of papers [START_REF] Cao | 1-generator quasi-cyclic codes over finite chain rings[END_REF][START_REF] Cui | Quaternary 1-generator quasi cyclic codes[END_REF][START_REF] Gao | 1-Generator quasi-cyclic and generalized quasi-cyclic codes over the ring Z 4 [u]/⟨u 2 -1⟩[END_REF][START_REF] Ozen | One generator quasi-cyclic codes over F 2 + vF 2[END_REF][START_REF] Seguin | A class of 1-generator quasi-cyclic codes[END_REF][START_REF] Siap | One generator quasi-cyclic codes over F 2 + uF 2[END_REF]. Here, we obtain the algebraic structure of 1-generator quasi-cyclic codes over R 3 by using their generators and minimal spanning sets. In short, three major contributions of the paper are:

1. The paper enumerates both self-dual (Theorem 4) and LCD (Theorem 5) double circulant codes over R q of length 2n where n is an odd integer. 2. It contains asymptotically good families of codes (Theorem 6). 3. It also presents the algebraic structure of 1-generator quasi-cyclic codes of length n over R q for q = 3 (Section 6). Further, it is proved that the Gray image of an s-QC code of length n is an sq-QC code of length nq over F q (Theorem 7).

The presentation of this paper is as follows: Section 2 recalls basic facts and definitions of the ring R q and double circulant codes. Section 3 enumerates double circulant self-dual codes of length 2n. In section 4, we discuss the asymptotic results for the families of LCD and self-dual double circulant codes. Next, section 5 contains numerical examples of double circulant LCD codes over R 3 . Section 6 focuses on 1-generator codes, while section 7 concludes the paper.

Preliminary

Let R q = F q + uF q + u 2 F q + • • • + u q-1 F q , u q = u. Thus, following [START_REF] Goyal | Duadic codes over the ring Fq[u]/⟨u m -u⟩ and their Gray images[END_REF][START_REF] Goyal | Quadratic residue codes over the ring Fp[u]/⟨u m -u⟩ and their Gray images[END_REF], R q is a finite commutative non-chain semi-local ring with unity. Also, the ring R q is isomorphic to the ambient ring F q [u]/⟨u q -u⟩, and every element r ∈ R q has a representation r = a 0 + ua 1 + • • • + a q-1 u q-1 where a i ∈ F q for 0 ≤ i ≤ q -1. Let α be a primitive element of F q and

η 1 = 1 -u q-1 , η 2 = 1 q -1 (u + u 2 + • • • + u q-2 + u q-1 ), η 3 = 1 q -1 (αu + α 2 u 2 + • • • + α q-2 u q-2 + u q-1 ), η 4 = 1 q -1 (α 2 u + (α 2 ) 2 u 2 + • • • + (α 2 ) q-2 u q-2 + u q-1 ), . . . η q = 1 q -1 (α q-2 u + (α q-2 ) 2 u 2 + • • • + (α q-2 ) q-2 u q-2 + u q-1 ).
Then it is checked that η 2 i = η i , η i η j = 0 for i ̸ = j, 1 ≤ i, j ≤ q and q i=1 η i = 1. In other words, {η i : 1 ≤ i ≤ q} is a set of pairwise orthogonal idempotent elements. Therefore, by using the Chinese Remainder Theorem, we have R q ∼ = q i=1 η i F q . Consequently, every element r ∈ R q can be expressed uniquely as r = q i=1 η i r i , where r i ∈ F q for all i. Moreover, r ∈ R q is a unit if and only if r i is a unit in F q for 1 ≤ i ≤ q. Now, we recall that a non-empty subset C of R n q is said to be a linear code of length n over R q if it is an R q -submodule of R n q and elements of C are called codewords. For any two vectors x = (x 1 , x 2 , . . . , x n ), y = (y 1 , y 2 , . . . , y n ), the Euclidean inner product is defined by x • y = n i=1 x i y i . In this way, the Euclidean dual of a linear code C is given by [START_REF] Ling | On the algebraic structure of quasi-cyclic codes II: Chain rings[END_REF] that a double circulant self-dual code over a commutative ring can only exist if a square root of -1 exists in that ring. The following theorem provides the conditions for the existence of the square root of -1 in the ring R q .

C ⊥ = {x ∈ R n q : x • y = 0, for all y ∈ C}. In addition, C is said to be self-dual if C = C ⊥ , self-orthogonal if C ⊆ C ⊥ and linear complementary dual (shortly, LCD) if C ∩ C ⊥ = {0}. It has been shown in
Theorem 1 In the ring R q with characteristic p, i.e., q = p s for s ≥ 1, a square root of -1 exists if and only if one of the following cases occurs:

1. p = 2, 2. p ≡ 3 (mod 4), and s is even 3. p ≡ 1 (mod 4)

Proof We already have that an square root of -1 exists in F q if and only if any one of the above cases occurs (see [START_REF] Ling | On the algebraic structure of quasi-cyclic codes II: Chain rings[END_REF]). Therefore, if any one of the above cases occurs then an square root of -1 exists in R q (since F q ⊆ R q ). Conversely, assume that r = q i=1 η i r i , where r i ∈ F q for all i, be an square root of -1 in R q , i.e., r 2 = -1 or equivalently r 2 + 1 = 0. Then

r 2 + 1 = 1 + η 1 r 2 1 + η 2 r 2 2 + • • • + η i r 2 q = η 1 (1 + r 2 1 ) + η 2 (1 + r 2 2 ) + • • • + η q (1 + r 2 q ) = 0
if and only if r 2 i = -1 for all i. That is, an square root of -1 exists in F q . Therefore, q is any one of the form given in above three cases.

⊓ ⊔

For a linear code C of length n over R q , we define

C 1 = {y 1 ∈ F n q | there exists y i (i ̸ = 1) ∈ F n q such that q i=1 y i η i ∈ C}, C 2 = {y 2 ∈ F n q | there exists y i (i ̸ = 2) ∈ F n q such that q i=1 y i η i ∈ C}, . . . C q = {y q ∈ F n q | there exists y i (i ̸ = q) ∈ F n q such that q i=1 y i η i ∈ C}.
Then C i is a linear code of length n over F q for 1 ≤ i ≤ q and C = q i=1 η i C i .

Proposition 1 Let C = q i=1
η i C i be a linear code of length n, where C i is a linear code of length n

over F q for 1 ≤ i ≤ q. Then C ⊥ = q i=1 η i C ⊥ i . Moreover, C is self-dual if and only if C i is self-dual for 1 ≤ i ≤ q.
Proof Same as the proof of [ [START_REF] Islam | A note on skew constacyclic codes over Fq + uFq + vFq[END_REF], Theorem 3.5].

⊓ ⊔

Again, we recall a linear code C is said to be a cyclic code if for any codeword (c 0 , c 1 , . . . , c n-1 ) ∈ C, we have (c n-1 , c 0 , . . . , c n-2 ) ∈ C. In addition, a cyclic code C can be described as an ideal of the ring

R q [x]/⟨x n -1⟩ by the correspondence (c 0 , c 1 , . . . , c n-1 ) ∈ C -→ c 0 + c 1 x + • • • + c n-1 x n-1 ∈ R q [x]/⟨x n -1⟩.
Here, the structural properties of cyclic codes over R q are already available in the literature [START_REF] Goyal | Duadic codes over the ring Fq[u]/⟨u m -u⟩ and their Gray images[END_REF] and we enlist them in the next result.

Theorem 2 Let C = q i=1
η i C i be a linear code of length n over R q . Then C is cyclic if and only if C i is a cyclic code for 1 ≤ i ≤ q. Further, C is principally generated by a polynomial g(x) = η 1 g 1 (x) + η 2 g 2 (x) + • • • + η q g q (x), a factor of x n -1, where g i (x) is the generator of C i for

1 ≤ i ≤ q.
Now, we define a Gray map ϕ : R q -→ F q q by ϕ(r) = (r 1 , r 2 , . . . , r q ) where r = q i=1 η i r i ∈ R q . Then ϕ is an F q -linear bijective map and can be extended to R n q componentwise. The Lee weight of x ∈ R n q is defined as w L (x) = w H (ϕ(x)) and the Lee distance between x, y ∈ R n q is d L (x, y) = d H (ϕ(x), ϕ(y)), where w H , d H are Hamming weight and distance in F nq q , respectively. Therefore, ϕ : R n q -→ F nq q is a distance preserving linear map.

Lemma 1 Let C be a linear code of length n over R q . Then ϕ(

C ⊥ ) = ϕ(C) ⊥ and ϕ(C ∩ C ⊥ ) = ϕ(C) ∩ ϕ(C) ⊥ .
Proof By the definition of Gray map ϕ, it is easily followed.

⊓ ⊔

In the light of Lemma 1, we immediately get the following result.

Theorem 3 Let C be a linear code of length n over R q . Then C is a self-dual (resp. LCD) code if and only if ϕ(C) is a self-dual (resp. LCD) code of length nq over F q . Now, we define the norm function N orm :

F q n → F q by N orm(a) = a q n -1 q-1 , for a ∈ F q n .
It is a multiplicative, surjective function with N orm(0) = 0 and every non-zero element of F q is a norm of exactly q n -1 q-1 elements in F q n (see [START_REF] Lidl | Finite Fields[END_REF]Theorem 2.28]). We will use N orm to find the number of solutions of certain algebraic equations. Recall that a double circulant code is a linear code having a generator matrix of the form

G = (I, A)
where A is a circulant matrix (i.e., the matrix whose rows can be obtained by successive circular shifts of the first row). For a family C ⟨n⟩ of codes over F q with parameters [n, k n , d n ], the rate ρ and relative distance δ are defined as ρ = lim sup n→∞ kn n and δ = lim sup n→∞ dn n . We say that this family of codes is good if ρδ ̸ = 0. Further, we recall the entropy function from [START_REF] Huffman | Fundamentals of Error Correcting Codes[END_REF] defined as

H q (x) = 0, if x = 0 x log q (q -1) -x log q (x) -(1 -x) log q (1 -x), if 0 < x ≤ 1 -1 q
and we will use it to show that the Gray images of family of self-dual (resp. LCD) double circulant codes over R q are good in subsequent portion.

Enumeration of double circulant codes

Let n be an odd integer and factorization of x n -1 into distinct irreducible factors over R q be given by

x n -1 = a(x -1) s i=2 g i (x) t j=1 h j (x)h * j (x),
where a ∈ R * q (set of units in R q ), g i (x) are self-reciprocal polynomials of even degree 2e i and h * j (x) are reciprocal polynomials of h j (x) with deg(h j (x)) = d j , for 2 ≤ i ≤ s and 1 ≤ j ≤ t. Now, by the Chinese Remainder Theorem, we have

R q [x] ⟨x n -1⟩ ∼ = R q [x] ⟨x -1⟩ ⊕ ⊕ s i=2 R q [x] ⟨g i (x)⟩ ⊕ ⊕ t j=1 R q [x] ⟨h j (x)⟩ ⊕ R q [x] ⟨h * j (x)⟩ ∼ =Rq ⊕ (⊕ s i=2 R q,2ei ) ⊕ ⊕ t j=1 R q,dj ⊕ R q,dj , where R q,r = F q r + uF q r + u 2 F q r + • • • + u q-1 F q r , u q = u for r = 2e i or d j .
From the natural extension of the above decomposition, we have

R q [x] ⟨x n -1⟩ 2 ∼ = R 2 q ⊕ ⊕ s i=2 (R q,2ei ) 2 ⊕ ⊕ t j=1 (R q,dj ) 2 ⊕ (R q,dj ) 2 .
Following this, any linear code C of length 2 over

Rq[x]

⟨x n -1⟩ can be decomposed as

C ∼ = C 1 ⊕ (⊕ s i=2 C i ) ⊕ ⊕ t j=1 (C ′ j ⊕ C ′′ j ) (1)
where C 1 is a linear code of length 2 over R q , C i is a linear code of length 2 over R q,2ei , for 2 ≤ i ≤ s and C ′ j , C ′′ j are linear codes of length 2 over R q,dj , for 1 ≤ j ≤ t. The following lemma is useful to enumerate self-dual and LCD double circulant codes over R q .

Lemma 2 Let C be a double circulant code of length 2n over R q given in the CRT decomposition [START_REF] Alahmadi | On self-dual double negacirculant codes[END_REF] with

α 1 = (1, c e1 ), α i = (1, c ei ), α ′ j = (1, c ′ dj ), α ′′ j = (1, c ′′ dj ) be generators of the constituent codes C 1 , C i over R q , R q,2ei and C ′ j , C ′′ j over R q,dj , respectively, for 2 ≤ i ≤ s, 1 ≤ j ≤ t. Then (1) C is a self-dual code if and only if 1 + c 2 e1 = 0, 1 + c 1+q e i ei = 0 and 1 + c ′ dj c ′′ dj = 0. (2) C is a Euclidean LCD code if and only if 1+c 2 e1 ∈ R * q , 1+c 1+q e i ei ∈ R * q,2ei and 1+c ′ dj c ′′ dj ∈ R * q,dj .
Proof The proof is similar to [START_REF] Shi | On self-dual and LCD double circulant and double negacirculant codes over Fq + uFq[END_REF]Lemma 3.1]. ⊓ ⊔ Now, by using Lemma 2, we count self-dual and LCD double circulant codes over R q in Theorem 4 and Theorem 5, respectively.

Theorem 4 Let n be an odd integer and the factorisation of x n -1 over R q be

x n -1 = a(x -1) s i=2 g i (x) t j=1 h j (x)h * j (x),
where a ∈ R * q and n = 1

+ s i=2 2e i + 2 t j=1 d j .
Then there are 2 q s (q ei + 1) q t j=1 (q dj -1) q self-dual double circulant codes of length 2n over R q .

Proof To obtain the total number of self-dual double circulant codes, we count the constituent codes. Let

c e1 ∈ R q . Then c e1 = a 1 η 1 + a 2 η 2 + • • • + a q η q for some a i ∈ F q , 1 ≤ i ≤ q. From Lemma 2, for the first constituent code C 1 , we need to find choices for c e1 ∈ R q such that 1 + c 2 e1 = 0. Consider 1 + c 2 e1 = 1 + a 2 1 η 1 + • • • + a 2 q η q = (1 + a 2 1 )η 1 + (1 + a 2 2 )η 2 + • • • + (1 + a 2 q )η q = 0,
if and only if 1 + a 2 i = 0 for 1 ≤ i ≤ q. So there are 2 choices (±ω, where ω 2 = -1 ) for each a i . Therefore, we have 2 q choices for c e1 and hence for C 1 .

For the second constituent code, we have to find choices for c ei ∈ R q,2ei such that 1+c ei c q e i ei = 0 where i is fixed. Let c ei = a 1 η 1 + a 2 η 2 + • • • + a q η q for some a j ∈ F q 2e i , 1 ≤ j ≤ q. Then 1 + c ei c q e i ei = 1 + a q e i +1 1

η 1 + • • • + a q e i +1 q η q = (1 + a q e i +1 1 )η 1 + • • • + (1 + a q e i +1 q
)η q = 0, if and only if a q e i +1 j = -1, i.e., N orm(a j ) = -1 for 1 ≤ j ≤ q. There are q ei + 1 solutions for each N orm(a j ) = -1, 1 ≤ j ≤ q. Thus, there are (q ei + 1) q choices for c ei .

In order to count the dual pairs (w.r.t. Euclidean inner product) of codes for fixed j, we have to find the choices for the pairs {c

′ dj , c dj ′′ } in R q,dj such that 1 + c ′ dj c ′′ dj = 0. Let c ′ dj = a 1 η 1 + a 2 η 2 + • • • + a q η q for some a i ∈ F q d j , 1 ≤ i ≤ q. Then, for c ′′ dj = b 1 η 1 + b 2 η 2 + • • • + b q η q where b i ∈ F q d j , 1 ≤ i ≤ q, we have 1 + c ′ dj c ′′ dj = (1 + a 1 b 1 )η 1 + (1 + a 2 b 2 )η 2 + • • • + (1 + a q b q )η q = 0, if and only if 1 + a i b i = 0, for all 1 ≤ i ≤ q. If a i ∈ F * q d j for 1 ≤ i ≤ q, then we have a unique choice b i = -1
ai , and if a i = 0, then we get 1 = 0, a contradiction. Therefore, a i ∈ F * q d j for each 1 ≤ i ≤ q and corresponding to each a i there is a unique choice for b i . Hence, there are (q dj -1) q choices for the dual pairs. Now, combining all the above cases, we get the desired result.

⊓ ⊔ Theorem 5 We assume the condition of Theorem 4. Then the total number of LCD double circulant codes of length 2n over R q is (q -2) q s i=2 (q 2ei -q ei -1) q t j=1 (q dj + (q dj -1) 2 ) q .

Proof As for the self-dual codes, the total number of LCD double circulant codes can be obtained by counting the constituent codes. For C 1 , we need to find the choices for

c e1 ∈ R q such that 1 + c 2 e1 ∈ R * q . If c e1 ∈ R q , then c e1 = a 1 η 1 + a 2 η 2 + • • • + a q η q for some a i ∈ F q , 1 ≤ i ≤ q. Now, 1 + c 2 e1 = 1 + a 2 1 η 1 + • • • + a 2 q η q = (1 + a 2 1 )η 1 + (1 + a 2 2 )η 2 + • • • + (1 + a 2 q )η q ∈ R * q ,
if and only if 1 + a 2 i ̸ = 0, for all 1 ≤ i ≤ q. That is, there are q -2 choices for each a i (̸ = ±ω, where ω 2 = -1 ). Therefore, we have (q -2) q choices for c e1 .

For a fixed 2 ≤ i ≤ s, to count second constituent codes C i , we need to find choices for

c ei ∈ R q,2ei such that 1 + c 1+q e i ei ∈ R * q,2ei . If c ei ∈ R q,2ei , then c ei = a 1 η 1 + a 2 η 2 + • • • + a q η q , for some a j ∈ F q 2e i , 1 ≤ j ≤ q. Now, 1 + c 1+q e i ei = 1 + a 1+q e i 1 η 1 + • • • + a 1+q e i q η q = (1 + a 1+q e i 1 )η 1 + • • • + (1 + a 1+q e i q )η q ∈ R * q,2ei ,
if and only if 1 + a 1+q e i j ̸ = 0, for all 1 ≤ j ≤ q. That is, there are q 2ei -q ei -1 choices for each a j , as we have q ei + 1 solutions for 1 + a q e i +1 j = 0. Therefore, we have (q 2ei -q ei -1) q choices for c ei . Now, for a fixed 1 ≤ j ≤ t, to count dual pairs {C ′ j , C ′′ j }, we need to find choices for c

′ dj , c ′′ dj ∈ R q,dj such that 1 + c ′ dj c ′′ dj ∈ R * q,dj . If c ′ dj ∈ R q,dj , then c ′ dj = a 1 η 1 + a 2 η 2 + • • • + a q η q , for some a i ∈ F q d j , 1 ≤ i ≤ q. Now, for any c ′′ dj = b 1 η 1 + b 2 η 2 + • • • + b q η q where b i ∈ F q d j , 1 ≤ i ≤ q, we have 1 + c ′ dj c ′′ dj = (1 + a 1 b 1 )η 1 + (1 + a 2 b 2 )η 2 + • • • + (1 + a q b q )η q ∈ R * q,dj
, if and only if 1 + a i b i ̸ = 0, for all 1 ≤ i ≤ q. We have the following possibilities for each a i , 1

≤ i ≤ q -If a i = 0, then 1 + a i b i = 1 ̸ = 0, for each b i ∈ F q d j . Therefore, there are q dj choices for b i . -If a i ∈ F * q d j , then 1 + a i b i ̸ = 0 implies that b i ̸ = -1
ai and we have q dj -1 choices for b i corresponding to the given a i . In this case, there are q dj -1 choices for a i , so we have (q dj -1) 2 choices for the pair {a i , b i } such that 1 + a i b i ̸ = 0.

Combining the above two possibilities, we have (q dj + (q dj -1) 2 ) q choices for the pairs {c ′ dj , c ′′ dj } in R q,dj and hence for {C ′ j , C ′′ j }. Now, from all the above discussion, we obtain the desired result. ⊓ ⊔

Distance bounds

Let n be an odd prime and q be a power of an odd prime such that it is a primitive root (mod n).

Then the factorization of x n -1 into distinct irreducible factors over R q is as follows:

x n -1 = (x -1)(1 + x + • • • + x n-1 ) = (x -1)h(x), (2)
where h(x) = 1 + x + • • • + x n-1 is an irreducible polynomial over R q . Hence, by the Chinese Remainder Theorem (CRT), we know that

R q [x] ⟨x n -1⟩ ∼ = R q [x] ⟨x -1⟩ ⊕ R q [x] ⟨h(x)⟩ ∼ =Rq ⊕ R ′ , where R ′ = F q n-1 + uF q n-1 + u 2 F q n-1 + • • • + u q-1 F q n-1 , u q = u. We denote R = Rq[x]
⟨h(x)⟩ . Any non-zero codeword of a cyclic code of length n is said to be a constant vector if it is generated by h(x). Now, we provide two lemmas which will be used to prove the main result related to distance bound (Theorem 6).

Lemma 3 For any non-zero vector z = (e, f ) ∈ R 2n q such that e is not a constant vector, there are at most q n(q-1)+1 double circulant codes C a = (1, a) over R q such that z ∈ C a .

Proof Using the CRT decomposition, we can write z = (e 1 , f 1 )⊕(e 2 , f 2 ). Since z ∈ C a , we have f = ea, f 1 = e 1 a 1 and f 2 = e 2 a 2 , where e 1 , f 1 , a 1 ∈ R q and e 2 , f 2 , a 2 ∈ R. Let a 1 = r 1 η 1 +r 2 η 2 +• • •+r q η q and a 2 = s 1 η 1 + s 2 η 2 + • • • + s q η q , for some r i ∈ F q and s i ∈ F q n-1 , 1 ≤ i ≤ q. Firstly, we discuss the choices for a 1 through e 1 .

If

e 1 ∈ R q , then e 1 = b 1 η 1 + b 2 η 2 + • • • + b q η q and f 1 = β 1 η 1 + β 2 η 2 + • • • + β q η q for some β i , b i ∈ F q , 1 ≤ i ≤ q. Now, f 1 = e 1 a 1 implies that β 1 η 1 + β 2 η 2 + • • • + β q η q = r 1 b 1 η 1 + r 2 b 2 η 2 + • • • + r q b q η q .
If b i = 0, then we have q choices for r i , otherwise r i = βi bi , i.e., a unique choice for r i . Therefore, there are at most q choices for each r i and hence at most q q choices for a 1 . Now, we discuss the choices for a 2 through e 2 . The following cases arise:

-If e 2 = 0, then e is a constant vector, i.e., e ≡ 0 (mod h(x)) and we get a contradiction to the choice of e.

-If 0 ̸ = e 2 ∈ R q , then e 2 = b 1 η 1 + b 2 η 2 + • • • + b q η q and f 2 = β 1 η 1 + β 2 η 2 + • • • + β q η q for some β i , b i ∈ F q n-1
, 1 ≤ i ≤ q and b i ̸ = 0 for at least one i. Now, f 2 = e 2 a 2 implies that

β 1 η 1 + β 2 η 2 + • • • + β q η q = s 1 b 1 η 1 + s 2 b 2 η 2 + • • • + s q b q η q .
If b i = 0, then we have q n-1 choices for s i , otherwise s i = βi bi , i.e., a unique choice for s i . Also, not all b i are zero. Therefore, we can conclude that there are at most q n-1 choices for each s i and at most q (n-1)(q-1) choices for a 2 .

Combining both the cases (for a 1 and a 2 ), we conclude that there are at most q n(q-1)+1 double circulant codes C a which contains z.

⊓ ⊔ Lemma 4 For any non-zero vector z = (e, f ) ∈ R 2n q such that e is not a constant vector, there are at most 2 q (1 + q n-1

2 ) (q-1) self-dual double circulant codes C a = (1, a) such that z ∈ C a .
Proof Using Theorem 4, we have at most q q choices for the first constituent code C 1 of C a . Now, we discuss the choices for the second constituent code, i.e., choices for a 2 through e 2 . Let

a 2 = s 1 η 1 + s 2 η 2 + • • • + s q η q , for some s i ∈ F q n-1 , 1 ≤ i ≤ q.
-If e 2 = 0, then e is a constant vector, i.e., e ≡ 0 (mod h(x)) and we get a contradiction to the choice of e.

-If 0 ̸ = e 2 ∈ R q , then e 2 = b 1 η 1 + b 2 η 2 + • • • + b q η q and f 2 = β 1 η 1 + β 2 η 2 + • • • + β q η q
for some β i , b i ∈ F q n-1 , 1 ≤ i ≤ q and b i ̸ = 0 for at least one i. Now, f 2 = e 2 a 2 implies that

β 1 η 1 + β 2 η 2 + • • • + β q η q = s 1 b 1 η 1 + s 2 b 2 η 2 + • • • + s q b q η q .
If b i = 0, then we have q n-1 choices for s i , otherwise s i = βi bi , i.e., a unique choice for s i . Also, we have 1 + a 2 ā2 = 1 + a 2 a q n-1 2

2

= 0 (since C a is self-dual). This implies that s i s q n-1 2 i = -1, i.e., N orm(s i ) = -1 for 1 ≤ i ≤ q. Therefore, we have at most 1 + q n-1 2 choices for each s i and hence (1 + q n-1

2 ) q-1 choices for each a 2 .

Combining these cases (for a 1 and a 2 ), we conclude that there are at most 2 q (1 + q n-1

2 ) q-1 double circulant codes C a which contains z.

⊓ ⊔

Using the Artin's conjecture [START_REF] Moree | Artin's primitive root conjecture a survey[END_REF] for primitive roots, we have that for a fixed non-square q, there are infinitely many primes n for which x n -1 factors into two irreducible polynomials given in (2) (since q is a primitive root modulo n). Therefore, we get an infinite family of double circulant codes over R and the following result can be derived.

Theorem 6 Let q be a power of an odd prime, and δ > 0 be given. Then there are families of double circulant self-dual (resp. LCD) codes of length 2n over R q , with code rate 1 2 , and with Gray images of relative distance δ as long as H q (δ) < 1 4q (resp. H q (δ) < 1 2q ). Moreover, we conclude that both of these families of codes are good.

Proof Let A n denote the size of the family. Then for large enough n (near infinity), by using Theorem 4 and Theorem 5, A n ≈ 2 q q (n-1)q 2

for self-dual and A n ≈ q nq for LCD double circulant codes. Let B(d n ) be the number of elements in R 2n q whose image under ϕ have Hamming weight less than d n . We assume that the inequality

A n > a n B(d n ), ( 3
)
where a n = 2 q (1 + q n-1

2 ) (q-1) for self-dual and q n(q-1)+1 , for LCD codes, is satisfied. Therefore, by Lemma 3 and Lemma 4, we conclude that in the family, there exist codes of length 2n over R q whose images under ϕ have Hamming distance ≥ d n . To enforce inequality (3) for large n, we make the following argument. We consider δ as the relative distance of the above family and assume that d n is the largest such that A n > a n B(d n ). Also, we assume that the growth is of the form d n = 2qδn. Then by [START_REF] Huffman | Fundamentals of Error Correcting Codes[END_REF]Lemma 2.10.3], we get B(d n ) is approximately equal to q 2qnHq(δ) . If H q (δ) = 1 2q for LCD, and = 1 4q for self-dual codes, then

a n B(d n ) ≈q n(q-1)+1 q 2qnHq(δ) = q nq+1 ≈ q nq a n B(d n ) ≈2 q (1 + q n- 1
2 ) (q-1) q 2qnHq(δ) ≈ 2 q q (n-1)(q-1) 2 q n 2 ≈ 2 q q (n-1)q 2

for LCD and self-dual codes, respectively. From this, we can see that if H q (δ) < 1 2q for LCD, and < 1 4q for self-dual codes, then inequality (3) holds for n large enough. ⊓ ⊔

Examples

In this section, we construct some examples of LCD double circulant codes over R q for q = 3 to validate our results. Let G = (I, A) be the generator matrix of a double circulant code C over R q = F q + uF q + • • • + u q-1 F q , u q = u, where I is the identity matrix of order n and

A = A 1 + uA 2 + • • • + u q-1 A q , for n × n matrices A 1 , A 2 , .
. . , A q over F q . Then the generator matrix of ϕ(C) is of order nq × 2nq whose rows are ϕ(G), ϕ(uG), . . . , ϕ(u q-2 G) and ϕ(u q-1 G), respectively.

In particular for q = 3 here we explicitly discuss its Gray map and generator matrix. In fact, for q = 3 we have

η 1 = 1 -u 2 , η 2 = u 2 +u 2 , η 3 = u 2 -u 2 .
Also, any element of R 3 can be written as

a + bu + cu 2 = aη 1 + (a + b + c)η 2 + (a -b + c)η 3 .
Therefore, the Gray map ϕ : R 3 -→ F 3 3 is defined by ϕ(a

+ bu + cu 2 ) = (a, a + b + c, a -b + c).
Now, let C be a double circulant code over R 3 = F 3 + uF 3 + u 2 F 3 with generator matrix of the form G = (I, A), where I is the identity matrix of order n and A = A 1 + uA 2 + u 2 A 3 , for n × n matrices A 1 , A 2 and A 3 over F 3 . Then the generator matrix of ϕ(C) is given by Ĝ

=   ϕ(G) ϕ(uG) ϕ(u 2 G)   =       I I I A 1 A 1 + A 2 + A 3 A 1 + 2A 2 + A 3 0 I 2I 0 A 1 + A 2 + A 3 2A 1 + A 2 + 2A 3 0 I I 0 A 1 + A 2 + A 3 A 1 + 2A 2 + A 3       3n×6n .
By using this generator matrix and the Magma computation system [START_REF] Bosma | Handbook of Magma Functions[END_REF], we now construct some LCD codes as F 3 -images of double circulant codes of length 2n over R 3 in Table 1. In second to fourth columns we have provided polynomials a i (x), for i = 1, 2, 3, respectively such that the generator polynomial of C over R 3 is (1, a(x)) where a(x) = a 1 (x) + ua 2 (x) + u 2 a 3 (x). Also, these polynomials are given (in Table 1) by their coefficients in decreasing powers of x. For example, 1234 represents the polynomial

x 3 + 2x 2 + 3x + 4. Example 1 Take α = 2, a primitive element of F 5 . Then η 1 = 1 -u 4 , η 2 = u+u 2 +u 3 +u 4 4 , η 3 = αu+α 2 u 2 +α 3 u 3 +u 4 4 , η 4 = α 2 u+u 2 +α 2 u 3 +u 4 4
and η 5 = α 3 u+α 2 u 2 +αu 3 +u 4 4 are pairwise orthogonal idempotent elements of R 5 . Also, an element r = a + bu + cu 2 + du 3 + eu 4 ∈ R 5 can be written as

r = aη 1 +(a+b+c+d+e)η 2 +(a+3b+4c+2d+e)η 3 +(a+4b+c+4d+e)η 4 +(a+2b+4c+3d+e)η 5 .
In that case, the Gray map ϕ : R 5 -→ F 5 5 is defined by ϕ(r) = (a, a + b + c + d + e, a + 3b + 4c + 2d + e, a + 4b + c + 4d + e, a + 2b + 4c + 3d + e). Now, let C = (1, a(x)) be a double circulant code of length 2n over R 5 , where a(x) = a 1 (x) + ua 2 (x) + u 2 a 3 (x) + u 3 a 4 (x) + u 4 a 5 (x). Then, ϕ(C) is a [10n, 5n]-code over F 5 . Moreover, duality is preserved under this map, i.e., the Gray image of self-dual (resp. LCD) code is a self-dual (resp. LCD) code.

(x) = x 2 + 3x + 3, a 2 (x) = x 2 + x + 2, a 3 (x) = 2x 2 + x + 1, a 4 (x) = x 2 + x + 2
and a 5 (x) = 2x 2 + x + 1, then C is a self-dual code and its Gray image ϕ(C) is also a self-dual code over F 5 with parameters [START_REF] Shi | Double circulant self-dual and LCD codes over Galois ring[END_REF][START_REF] Islam | A note on skew constacyclic codes over Fq + uFq + vFq[END_REF][START_REF] Cao | 1-generator quasi-cyclic codes over finite chain rings[END_REF].

6 1-generator quasi-cyclic (QC) codes

In the present section, we discuss the algebraic structure of 1-generator quasi-cyclic (QC) code over R q for q = 3. It is worth mentioning that 1-generator quasi-cyclic codes for q = 2 are extensively studied in [START_REF] Ozen | One generator quasi-cyclic codes over F 2 + vF 2[END_REF]. They obtained their minimal spanning sets and binary Gray images. The 1-generator QC codes over R q for any q > 3 can be obtained but for the sake of calculation, here we restrict to q = 3. Now, we start our discussion with the definition of QC codes.

Definition 1 Let C be a linear code over R q of length n = sl and σ be the cyclic shift operator on R n q . Then C is said to be a quasi-cyclic (QC) code with index s (or s-QC code), if σ s (C) = C. Evidently, if s = 1, then C is a cyclic code.

Definition 2 A quasi-cyclic (QC) code over R q generated by a single element is called a 1generator quasi-cyclic code.

Note that any two polynomials p(x) and q(x) in R q [x] are said to be relatively prime if there exist two polynomials m 1 (x), m 2 (x) ∈ R q [x] such that p(x)m 1 (x) + q(x)m 2 (x) = 1. Based on this, we provide a result which will be used to study 1-generator quasi-cyclic (QC) codes.

Lemma 5 [START_REF] Ozen | One generator quasi-cyclic codes over F 2 + vF 2[END_REF]Lemma 2.4] Let C = ⟨g(x)⟩ be a cyclic code of length n over R q with generator polynomial g(x). Then C = ⟨g(x)f (x)⟩ for any polynomial f (x) such that f (x) and x n -1 g(x) are relatively prime.

Theorem 7 Let C be an s-QC code of length n = sl over R q . Then ϕ(C) is an sq-QC code of length nq over F q .

Proof Let C be an s-QC code over R q and v = (v 11 , v 12 , . . . , v 1s , v 21 , v 22 , . . . , v 2s , . . . , v l1 , v l2 , . . . , v ls ) ∈ C, where

v ij = q k=1 η k r (k) ij for 1 ≤ i ≤ l, 1 ≤ j ≤ s. Then σ s (v) ∈ C and ϕ(v) =(r
1s , r

1s , . . . , r (q) 1s , . . . , r

l-11 , r

l-11 , . . . , r (q) l-11 , . . . , r

l-1s , r

l-1s , . . . , r (q) l-1s ) =ϕ(v l1 , v l2 , . . . , v ls , v 11 , v 12 , . . . , v 1s , . . . , v l-11 , v l-12 , . . . , v l-1s ) =ϕσ s (v) ∈ ϕ(C).

Thus, ϕ(C) is an sq-QC code of length nq over F q .

⊓ ⊔

Let C be an s-QC code of length n = sl over R q . Then we can define a one-one correspondence

Γ : R n q → R s q,l by Γ (v 11 , v 12 , . . . , v 1s , v 21 , v 22 , . . . , v 2s , . . . , v l1 , v l2 , . . . , v ls ) = (v 1 (x), v 2 (x), . . . , v s (x)), where v j (x) = l i=1 v ij x i-1 and R q,l = Rq[x]
⟨x l -1⟩ . It can be easily seen that an s-QC code of length n = sl over R q corresponds to an R q,l -submodule of R s q,l . Theorem 8 Let C be a 1-generator s-QC code of length n = sl over R

3 = F 3 + uF 3 + u 2 F 3 , where u 3 = u. If C is generated by G(x) = (G 1 (x), G 2 (x), . . . , G s (x)) where G i (x) ∈ R 3,l = R 3 [x]/ x ℓ -1 , then G i (x) ∈ B i for some cyclic codes B i in R 3,l , 1 ≤ i ≤ s and there exist polynomials f i (x) ∈ R 3 [x], r (j) i (x) ∈ F 3 [x], 1 ≤ i ≤ s, j = 1, 2, 3 such that G i (x) = f i (x)(η 1 r (1) i (x)+ η 2 r (2) i (x) + η 3 r (3) i (x)). Proof Let C be a 1-generator s-QC code of length n = sl over R 3 generated by G(x) = (G 1 (x), G 2 (x), . . . , G s (x)). Then Γ i (C) is a cyclic code where Γ i is the i-th projection defined as Γ i (G 1 (x), G 2 (x), . . . , G s (x)) = G i (x)
. Therefore, using Theorem 2 and Lemma 5 we get that a generator

G i (x) of Γ i (C) is of the form G i (x) = f i (x)(η 1 r (1) i (x) + η 2 r (2) i (x) + η 3 r (3) i (x)) for some polynomials f i (x) ∈ R 3 [x], r (j) i (x) ∈ F 3 [x], 1 ≤ i ≤ s, j = 1, 2, 3. ⊓ ⊔ Note that G i (x) can also be written in the form G i (x) = a i (x)η 1 + b i (x)η 2 + c i (x)η 3 for some polynomials a i (x), b i (x), c i (x) ∈ F 3 [x], 1 ≤ i ≤ s.
The following theorem provides a minimal generating set for a 1-generator s-QC code C over R 3 .

Theorem 9 Let C be a 1-generator s-QC code over R 3 of length n = sl and the generator

G(x) =(a 1 (x)η 1 + b 1 (x)η 2 + c 1 (x)η 3 , . . . , a s (x)η 1 + b s (x)η 2 + c s (x)η 3 )
where

a i (x), b i (x), c i (x) ∈ F 3 [x], for all 1 ≤ i ≤ s. Let g(x) = gcd(a 1 (x)η 1 + b 1 (x)η 2 + c 1 (x)η 3 , . . . , a s (x)η 1 + b s (x)η 2 + c s (x)η 3 , x l -1),
and h(x) be a polynomial such that

g(x)h(x) = x l -1. Then C is free R 3 -submodule with basis B = deg(h)-1 i=0 {x i G(x)} and rank(C) = deg(h(x)). Proof Any codeword c(x) ∈ C is of the form c(x) = f (x)G(x), where f (x) ∈ R 3 [x]. If deg(f (x)) ≤ deg(h(x)) -1, then c(x) = f (x)G(x) ∈ span(B). Otherwise, by division algorithm f (x) = h(x)q 1 (x) + s 1 (x) for some q 1 (x), s 1 (x) ∈ R 3 [x] where deg(s 1 (x)) ≤ deg(h(x)) -1. Then f (x)G(x) =(h(x)q 1 (x) + s 1 (x))G(x)
=q 1 (x)h(x)G(x) + s 1 (x)G(x), where s 1 (x)G(x) ∈ span(B).

Since h(x)(a i (x)η 1 +b i (x)η 2 +c i (x)η 3 ) = 0 for all 1 ≤ i ≤ s, we have q 1 (x)h(x)G(x) = (0, 0, . . . , 0) ∈ span(B). Therefore, B spans C. Now, we show that none of the element of B can be written as the linearly combination of other elements of B. Let α 0 , α 1 , . . . , α t-1 ∈ R 3 where t = deg(h(x)) be such that t-1 j=0 α j x j G(x) = 0, i.e., t-1 j=0 α j x j (a i (x)η 1 + b i (x)η 2 + c i (x)η 3 ) = 0, for all 1 ≤ i ≤ s.

Comparing the constant term on both sides of the above equation, we get α 0 (a i η 1 +b i η 2 +c i η 3 )(0) = 0, where (a i η 1 + b i η 2 + c i η 3 )(0) is invertible (since each of a i (0), b i (0), c i (0) are non-zero). This implies α 0 = 0. Substituting the value of α 0 and comparing the coefficients of x in (4), we get α 1 = 0. Similarly, α j = 0 for all 0 ≤ j ≤ t -1. That is, B is linearly independent and hence none of the element of B belongs to the span of remaining elements of B.

⊓ ⊔

Theorem 10 Let C be a 1-generator s-QC code of length n = sl over R 3 generated by G(x) = (g(x)f 1 (x), g(x)f 2 (x), . . . , g(x)f s (x)) for some divisor g(x) of x l -1 and gcd(f i (x), x l -1 g(x) ) = 1 for each 1 ≤ i ≤ s. Then B ′ = {G(x), xG(x), . . . , x l-t-1 G(x)}, where deg(g(x)) = t is a basis for C and d L (C) s ≥ d L (C ′ ), where C ′ = (g(x)) is a cyclic code of length l over R 3 .

Proof The proof is similar to [START_REF] Ozen | One generator quasi-cyclic codes over F 2 + vF 2[END_REF]Theorem 3.7].

⊓ ⊔ Now, we present an example as suggested by Theorem 10 and obtain a ternary 6-QC code as below.

Example 2 Let l = 10 and g 1 (x) = g 2 (x) = (x + 2)(x 4 + 2x 3 + x 2 + 2x + 1) = x 5 + x 4 + 2x 3 + x 2 + 2x + 2, g 3 (x) = (x + 1)(x 4 + x 3 + x 2 + x + 1) = x 5 + 2x 4 + 2x 3 + 2x 2 + 2x + 1.

Then g 1 (x), g 2 (x), g 3 (x) are factors of x 10 -1 in F 3 [x]. Therefore C ′ = ⟨g(x)⟩ is a cyclic code of length 10 over R 3 = F 3 + uF 3 + u 2 F 3 , where g(x) = 3 i=1 η i g i (x). Hence, C ′ has 9 5 = 59049 codewords and minimum Lee distance 4. Also, by Theorem 10, C is a 2-QC code given by G(x) = ⟨g(x)f 1 (x), g(x)f 2 (x)⟩, where f 1 (x), f 2 (x) satisfying the conditions mentioned in Theorem 10. In this way, C has the parameters [20, 5, ≥ 8] and its ternary image [60, 15, ≥ 8] is a 6-QC code.

Conclusion

The main purpose of the article is to enumerate self-dual and LCD double circulant codes over R q whose Gray images (both self-dual and LCD) are proved to be good enough. In addition, algebraic properties of 1-generator QC codes are obtained. Besides, we have also provided several examples of LCD double circulant codes over R 3 . It is worth mentioning that self-dual double circulant codes do not exist over R 3 due to Theorem 1. Therefore, like Table 1, it would be worthwhile to compute numerical examples of self-dual double circulant codes over R q for the q's meeting the hypotheses of Theorem 1. Further, one can derive similar results for more general ring F q [u]/⟨f (u)⟩ (appeared in [START_REF] Goyal | Duadic negacyclic codes over a finite non-chain ring[END_REF]), where f (u) splits into linear factors over F q .

  sq (ϕ(v)) =(r(1) l1 , r (2) l1 , . . . , r (q) l1 , . . . , r(1)ls , r(2)ls , . . . , r(q) ls , r(1) 11 , r(2) 11 , . . . , r (q) 11 , . . . , r

Table 1 :

 1 LCD codes from Gray images of double circulant codes of length 2n overR 3 If n = 2, take a 1 (x) = 2x, a 2 (x) = x + 2, a 3 (x) = 2x + 3, a 4 (x) = 4xand a 5 (x) = x + 2, then C is a self-dual code and its Gray image ϕ(C) is also a self-dual code over F 5 with parameters [20, 10, 2]. 2. If n = 3, take a 1

	n	a 1 (x)	a 2 (x)	a 3 (x)	ϕ(C) (LCD)
	7	1021112	1101200	21011211	[42, 21, 5] 3
	8	21121012	02120112	12100222	[48, 24, 5] 3
	11	12101202112	12122221212	01222022111	[66, 33, 6] 3
	12	121012221120	202222100221	220222112012	[72, 36, 6] 3
	13	1210122011212	2122221002212	2222221120122	[78, 39, 7] 3
	14	12101220112122	21222210022122	22222211201222	[84, 42, 7] 3
	16	1210222021222022	2212202210201121	2022202221120102	[96, 48, 8] 3
	17 12121222211212220	02122022102021202	20222222211201002	[102, 51, 8] 3
	1.