Artiom Alhazov
email: artiom@math.md

Sergey Verlan
email: verlan@u-pec.fr

Rudolf Freund

Small Universal Reversible Counter Machines

come

Introduction

Universality is a fundamental concept in the theory of computation. The question of finding a universal computing device in the class of Turing machines was originally proposed by A. Turing himself in [START_REF] Turing | On computable numbers, with an application to the Entscheidungsproblem[END_REF]. A universal Turing machine would be capable of simulating any other Turing machine T : given a description of T and the encoding of the input tape contents, the universal machine would halt with tape contents which would correspond to the encoding of the output of T for the supplied input.

In a more general setting of an arbitrary class C of computing devices, the universality problem consists in finding such a fixed element M 0 which would be able to simulate any other element M ∈ C. More formally, if the result of running M with the input x is y (usually written as M (x) = y), then y = f (M 0 (g(M ), h(x)), where g is the function enumerating C, while f and h are the decoding and encoding functions respectively. We remark that in some cases it can be possible to have M 0 ∈ C; then the input is the couple encoding of g(M ) and x (e.g. using the Cantor pairing function). It is generally agreed that f and h should not be "too" complicated. Since it is relatively common to rely on exponential coding when working with devices computing numbers, the functions f (x) = log a (x) and h(x) = b x , for some a, b ∈ N are often used (cf. [START_REF] Minsky | Computations: Finite and Infinite Machines[END_REF][START_REF] Woods | The complexity of small universal Turing machines: A survey[END_REF]).

In this paper, we will adhere to the terminology established by I. Korec in [7] and call the element M 0 defined as above weakly universal (or just universal). In case the functions f and h are additionally required to be identities, M 0 will be referred to as strongly universal. Hence, the strong universality permits to capture the situations when the encoding does not alter the power of the device. For example, 2-register machines are weakly universal [START_REF] Minsky | Computations: Finite and Infinite Machines[END_REF], but they cannot be strongly universal as they cannot compute even the square function [START_REF] Barzdin | Ob odnom klasse machin Turinga (machiny Minskogo), russian[END_REF][START_REF] Schroeppel | A two counter machine cannot calculate 2N[END_REF].

As a further development on the question of universality, C. Shannon [16] considered finding the smallest possible universal Turing machine, where the size is essentially given by the sizes of the alphabets of symbols and states. A series of important results concerning this direction were obtained [START_REF] Minsky | Size and structure of universal Turing machines using tag systems[END_REF]14,18]. For an overview of the recent results the reader is referred to [13]. Small universal devices are of considerable theoretical importance since they indicate the minimal choice ingredients sufficient for achieving computational completeness.

A k-counter machine (CM(k)) is an automaton with k counters that can hold non-negative values. In one step, the finite-state control of CM(k) can increment or decrement the contents by one or test whether it is zero or not. A related model is the register machine [START_REF] Minsky | Computations: Finite and Infinite Machines[END_REF], having eventual restrictions on the form of the control and a richer set of potential instructions. However, the common variant of register machines is almost identical to CMs. Register machines and hence CMs were shown to be universal and it is known that already three registers/counters suffice for strong universality and two for the weak one [START_REF] Ivanov | Small universal non-deterministic Petri nets with inhibitor arcs[END_REF][START_REF] Minsky | Computations: Finite and Infinite Machines[END_REF].

In [10] K. Morita studied reversible CMs and showed the universality of reversible CM [START_REF] Axelsen | What do reversible programs compute?[END_REF]. These machines are backward deterministic, i.e., each configuration has at most one predecessor. This research lines up in the study of other reversible systems such as reversible Turing machines, reversible cellular automata and reversible logic gates, see [START_REF] Bennett | Notes on the history of reversible computation[END_REF][START_REF] Morita | Reversible cellular automata[END_REF] for a general survey. We remark that in case of reversible machines, the notion of universality is slightly different than in the classical case [START_REF] Axelsen | What do reversible programs compute?[END_REF].

In 1996, I. Korec described a number of universal register machines with considerably fewer instructions than were known to be needed for universality before [7]. Based on this result small 2-and 3-register machines were constructed [1].

In this paper we consider the construction of small universal reversible counter machines. As in [7,[START_REF] Morita | Universal reversible Turing machines with a small number of tape symbols[END_REF]1] we are mainly interested in the number of instructions as well as in the trade-offs between this number an the number of counters. We construct four small universal reversible counter machines highlighting different trade-offs: (10, 109, 129), [START_REF] Morita | Reversible cellular automata[END_REF]227,270), [START_REF] Minsky | Computations: Finite and Infinite Machines[END_REF]97,116) and [START_REF] Axelsen | What do reversible programs compute?[END_REF]1097,1568), where in parentheses we indicated the number of counters, the number of states and the number of instructions, respectively.

Definitions

We now recall the formal definition of CM given in [10]. We denote by N the set of all non-negative integers.

Definition 1. A k-counter machine (CM(k)) is the 5-tuple M = (k, Q, δ, q 0 , q f ),
where k is the number of counters, Q is a nonempty finite set of states, q 0 ∈ Q is the initial state, q f ∈ Q is the final (halting) state and δ is the move relation, which is a

subset of Q × {1, . . . , k} × {Z, P} × Q ∪ Q × {1, . . . , k} × {-, 0, +} × Q.
We will use the notation Ri to denote the counter i.

Definition 2. An instantaneous description of a CM(k) M = (k, Q, δ, q 0 , q f ) is a k + 1-tuple (q, n 1 , . . . , n k ) ∈ Q × N k .
The transition relation is defined as follows:

(q, n 1 , . . . , n i , . . . , n k ) (q, n 1 , . . . , n i , . . . , n k ) iff one of the following conditions is satisfied:

1. [q, i, Z, q ] ∈ δ and n i = n i = 0 (the zero test instruction). 2. [q, i, P, q ] ∈ δ and n i = n i > 0 (the non-zero instruction). 3. [q, i, -, q ] ∈ δ and n i -1 = n i (the minus instruction). 4. [q, i, 0, q ] ∈ δ and n i = n i (the jump instruction). 5. [q, i, +, q ] ∈ δ and n i + 1 = n i (the plus instruction).

In order to define the computation of the counter machine we need to consider input and output counters. Without losing the generality, we may assume that the input counters are numbered from 1 to i and the output ones are numbered from j to l. Then the result of the computation of M on the vector (n 1 , . . . , n i ) can be defined as follows:

M (n 1 , . . . , n i ) = {(n j , . . . , n l ) | (q 0 , n 1 , . . . , n i , 0, . . . , 0) * (q f , n 1 , . . . , n k )}.
According to Korec [7], a machine M is (weakly) universal if there exist recursive functions h and g such that for any machine M we have

M (x) = f (M (# M , h(x)))
, where # M is the number of M in some enumeration.

A machine is said to be strongly universal if f and h are identities. In [7] it was shown that there exist a strongly universal register machine U 32 with 32 instructions and a weakly universal register machine with 29 instructions. While the model of register machine used in [7] is slightly different from Definition 1, there is no difficulty in translating it to/from the form used in this paper. Moreover, this translation keeps the same number of states and basically the same number of instructions (with the remark that zero-test instructions from register machines correspond to two instructions in the counter machine). We give below the corresponding list of instructions. Note that this translation adds two additional states that are not considered in [7] for technical reasons: q 0 and q f corresponding to the start and the end state respectively. Hence, the resulting machine U 34 has 46 instructions. Notice also that U 32 is numbering registers from 0 to 7. We recall that the code of the simulated machine is initially stored in R1, the initial value in R2 and the result is obtained in R0. At the end of the computation all values of counters R3-R7 are bounded.

[q 1 , 1, P, q 2 ] [q 1 , 1, Z, q 6 ] [q 2 , 1, -, q 3 ] [q 3 , 7, +, q 1 ]
[q 4 , 5, P, q 5 ] [q 4 , 5, Z, q 7 ] [q 5 , 5, -, q 6 ] [q 6 , 6, +, q 4 ] [q 7 , 6, P, q 8 ] [q 7 , 6, Z, q 4 ] [q 8 , 6, -, q 9 ] [q 9 , 5, +, q 10 ] [q 10 , 7, P, q 11 ] [q 10 , 7, Z, q 13 ] [q 11 , 7, -, q 12 ] [q 12 , 1, +, q 7 ] [q 13 , 6, P, q 14 ] [q 13 , 6, Z, q 1 ] [q 14 , 4, P, q 15 ] [q 14 , 4, Z, q 16 ] [q 15 , 4, -, q 1 ] [q 16 , 5, P, q 17 ] [q 16 , 5, Z, q 23 ] [q 17 , 5, -, q 18 ] [q 18 , 5, P, q 19 ] [q 18 , 5, Z, q 27 ] [q 19 , 5, -, q 20 ] [q 0 , 1, 0, q 1 ] [q 20 , 5, P, q 21 ] [q 20 , 5, Z, q 30 ] [q 21 , 5, -, q 22 ] [q 22 , 4, +, q 16 ] [q 23 , 2, P, q 24 ] [q 23 , 2, Z, q 25 ] [q 24 , 2, -, q 32 ] [q 25 , 0, P, q 26 ] [q 25 , 0, Z, q 32 ] [q 26 , 0, -, q 1 ] [q 27 , 3, P, q 28 ] [q 27 , 3, Z, q 29 ] [q 28 , 3, -, q 32 ] [q 29 , 0, +, q 1 ] [q 30 , 2, +, q 31 ] [q 31 , 3, +, q 32 ] [q 32 , 4, P, q 15 ] [q 32 , 4, Z, q f ] As for register machines, counter machines can be represented in a graphical manner as a graph whose nodes are labeled by elements from Q and having a directed edge going from q to q labeled by iX if [q, i, X, q ] ∈ δ, see e.g. Fig. 1.

A CM M is said to be deterministic if for any pair of instructions [p, i, X, p ] and [q, j, Y, q ] from δ it holds

p q ∨ (i = j ∧ X Y ∧ X, Y {-, 0, +}) .
A CM M is said to be reversible if if for any pair of instructions [p, i, X, p ] and [q, j, X, q ] from δ it holds

p q ∨ (i = j ∧ X Y ∧ X, Y {-, 0, +}).
In the graphical form the deterministic property implies that each node has at most two outgoing arcs. In the case of two arcs, both of them should correspond to the zero and non-zero test of the same counter. Since U 32 is deterministic, it is not surprising that U 34 is deterministic too.

Similarly, the reversible property implies that each node has at most two incoming arcs. As in the deterministic case, when there are two incoming arcs then both of them should correspond to the zero and non-zero test of the same counter. We will call non-reversible a node (state) that is not fulfilling this property.

We also recall the following results from [10]:

Theorem 1 ([10], Theorem 3.1). For any deterministic CM(k) M = (k, Q, δ, q 0 , q f ), there is a deterministic reversible CM(k + 2) M = (k + 2, Q , δ , q 0 , q f ) such that (q 0 , m 1 , . . . , m k ) * M (q f , n 1 , . . . , n k ) iff ∃h ∈ N (q 0 , m 1 , . . . , m k , 0, 0) * M (q f , n 1 , . . . , n k , h, 0)
holds for all m 1 , . . . , m k , n 1 , . . . , n k ∈ N.

The proof of above theorem produces the history of the computation, which is recorded in the value h using a method from [4]. Obviously, this value is not known in advance and it is not bounded. The next theorem shows that using k additional counters it is possible to bound it, hence obtaining each time a "clean" computation where only the value of the output is not bounded in advance. We should call such machines garbage-less.

Theorem 2 ([10], Theorem 3.2). For any deterministic CM(k)

M = (k, Q, δ, q 0 , q f ), there is a deterministic reversible CM(2k + 2) M = (2k + 2, Q , δ , q 0 , q f ) such that (q 0 , m 1 , . . . , m k ) * M (q f , n 1 , . . . , n k ) iff (q 0 , m 1 , . . . , m k , 0, . . . , 0) * M (q f , m k , . . . , m k , 0, 0, n 1 , . . . , n k )
holds for all m 1 , . . . , m k , n 1 , . . . , n k ∈ N.

Next theorem shows that as in [START_REF] Minsky | Computations: Finite and Infinite Machines[END_REF] any number of counters can be packed into two in a reversible manner.

Theorem 3 ([10], Theorem 4.1). For any deterministic CM(k)

M = (k, Q, δ, q 0 , q f ), there is a deterministic reversible CM(2) M = (2, Q , δ , q 0 , q f ) such that (q 0 , m 1 , . . . , m k ) * M (q f , n 1 , . . . , n k ) iff (q 0 , p m 1 1 . . . p m k k , 0) * M (q f , p n 1 1 . . . p n k k , 0)
holds for all m 1 , . . . , m k , n 1 , . . . , n k ∈ N, where p i denotes the ith prime number.

Strong Universality

In this section we will construct several small universal reversible counter machines. We start by analyzing the machine U 34 . It can be easily seen that U 34 has the following non-reversible states: q 1 , q 4 , q 6 , q 7 , q 15 , q 16 , q 32 .

States q 1 and q 32 are non-reversible because of multiple incoming arcs (6 and 4 respectively). The other states are non-reversible because the incoming arcs do not correspond to opposite checks of the same counter.

We start by reducing the number of incoming arcs to each state to at most four. This is performed by adding two additional states as in [10], Lemma 3.1. We remark that added states are non-reversible. This yields the following machine U 36 , see also Fig. 1 (we emphasized in bold the differences with respect to the U 34 machine):

[q 1 , 1, P, q 2 ]
[q 1 , 1, Z, q 6 ] [q 2 , 1, -, q 3 ] [q 3 , 7, +, q 34 ] [q 4 , 5, P, q 5 ] [q 4 , 5, Z, q 7 ] [q 5 , 5, -, q 6 ] [q 6 , 6, +, q 4 ] [q 7 , 6, P, q 8 ] [q 7 , 6, Z, q 4 ] [q 8 , 6, -, q 9 ] [q 9 , 5, +, q 10 ] [q 10 , 7, P, q 11 ] [q 10 , 7, Z, q 13 ] [q 11 , 7, -, q 12 ] [q 12 , 1, +, q 7 ] [q 13 , 6, P, q 14 ] [q 13 , 6, Z, q 33 ] [q 14 , 4, P, q 15 ] [q 14 , 4, Z, q 16 ] [q 15 , 4, -, q 33 ] [q 16 , 5, P, q 17 ] [q 16 , 5, Z, q 23 ] [q 17 , 5, -, q 18 ] [q 18 , 5, P, q 19 ] [q 18 , 5, Z, q 27 ] [q 19 , 5, -, q 20 ] [q 0 , 1, 0, q 1 ] [q 20 , 5, P, q 21 ] [q 20 , 5, Z, q 30 ] [q 21 , 5, -, q 22 ] [q 22 , 4, +, q 16 ] [q 23 , 2, P, q 24 ] [q 23 , 2, Z, q 25 ] [q 24 , 2, -, q 32 ] [q 34 , 1, 0, q 1 ] [q 25 , 0, P, q 26 ] [q 25 , 0, Z, q 32 ] [q 26 , 0, -, q 33 ] [q 33 , 1, 0, q 34 ] [q 27 , 3, P, q 28 ] [q 27 , 3, Z, q 29 ] [q 28 , 3, -, q 32 ] [q 29 , 0, +, q 33 ] [q 30 , 2, +, q 31 ] [q 31 , 3, +, q 32 ] [q 32 , 4, P, q 15 ] [q 32 , 4, Z, q f ] Note that it was possible to reduce in the same manner the number of incoming arcs to two. Then it is possible to use the construction from Theorem 1 in order to construct an equivalent reversible machine. In this case each pair of arcs (instructions) leading to a non-reversible state are replaced by 21 instructions and 16 additional states. A quick computation shows that using this method a strongly universal reversible machine with 273 instructions and 235 states is obtained.

We show below that for U 36 a more efficient construction can be used. We will use a modified version of the technique from Theorem 1. We recall that the core of this proof is that in order to make non-reversible states reversible an additional counter is used to keep track of the computation history. More precisely, this counter stores a number whose bits keep track of which of the two incoming arcs was used to reach a non-reversible state. Another additional counter is needed for technical reasons.

q 1 q 2 q 3 1- 1P q 0 JMP 7+ q 4
q 5 q 6

5-5P 1Z q 7 q 8 q 9

6-6P 6+ 5Z 6Z q [START_REF] Morita | Universal reversible Turing machines with a small number of tape symbols[END_REF] q 11 q 10 7P 7-1+ 5+ q 13 q 14 7Z 6P 6Z q [START_REF] Schroeppel | A two counter machine cannot calculate 2N[END_REF] 4-4P q 16 q 19 q 17 q 18 q 23 q 21 q 22 q 20 q 25 q 26 q 28 q 27 q 29 q 30 q 31 q 32 q f 5P 4Z 5- With the goal of minimization of the number of instructions and states we allow up to four incoming arcs to a node. Hence, our history will keep a base-4 representation of the used choice. We start by the observation that in the case of state q 4 the incoming arcs are labeled by 6Z and 6+. We introduce a new state q 4 and we replace the instruction [q 6 , 6, +, q 4 ] by two instructions: [q 6 , 6, +, q 4 ], [q 4 , 6, P, q 4 ] A similar transformation is done for the state q 16 (using counter R4).

Next, we observe that the two jump instructions at state q 1 can be replaced by the test of counter R8 that is supposed to store the history of the computation (recall that the construction from Theorem 1 adds two additional counters R8 and R9). Since at the beginning of the computation the history is empty (equal to zero) and after the first cycle returning to q 1 it is not empty, it is possible to correctly discriminate both cases:

[q 0 , 8, Z, q 1 ], [q 34 , 8, P, q 1 ] Now we concentrate on the state q 34 . On one branch the counter R7 is positive (because of the R7+ instruction). On the other branch counter R7 is always zero, because the last operation on R7 that is performed in order to reach q 34 is the instruction [q 10 , 7, Z, q 13 ] that ensures that R7 is empty. Hence, it is possible to use the following instructions to make q 34 reversible: [q 3 , 7, +, q 3 ], [q 3 , 7, P, q 34 ], [q 33 , 7, Z, q 34 ] Consider now the state q 15 . Using the flowchart depicted at Fig. 1 it can be easily verified that the value of counter R5 can discriminate the two branches. Indeed, the instruction [q 9 , 5, +, q 10 ] ensures that R5 is positive when going to q 15 from q 14 . On the other hand, in order to reach q 32 one has to pass through q 23 , q 27 or q 30 . But this implies a zero test on R5. Hence, we can use following instructions to obtain the reversible behavior of q 15 : [q 32 , 4, P, q 32 ], [q 32 , 5, Z, q 15 ], [q 14 , 4, P, q 14 ], [q 14 , 5, P, q 15 ] Thus, only 4 states (q 6 , q 7 , q 32 , q 33 ) need to be made reversible. We describe below the procedure that allows to replace any node with at most four incoming edges by an equivalent reversible construction.

Consider a state q t that has 4 incoming arcs. Let the corresponding instructions be [q s j , i s j , X j , q t ], 1 ≤ j ≤ 4. Then consider the following rules (depicted also on Fig. 2): q t1 q t2 q t3 q t5 q t7 q t9 q t4 q t6 q t8 q t10

8-9+

9P 9+ 9P 9+ 9P 9+ 9P 8P q t11 q t12 q t13 q t q t14 8Z 9- 8+ 9Z 9P 8P q s4 q s41 i s4 X 4 9Z q s3 q s31 i s3 X 3 9Z q s2 q s21 i s2 X 2 9Z q s1 q s11 i s1 X 1 9Z
Fig. 2 Reversible junction of 4 instructions in q t . states from U 36 , plus 5 additional states used for the reversibility of q 1 , q 4 , q 15 , q 16 and q 34 , plus 2 × 18 states used for the reversibility of q 32 and q 33 , plus 2 × 16 states used for the reversibility of q 6 and q 7 ) and 129 instructions (48

+ 5 + 2 × 20 + 2 × 18).
Theorem 4. There exists a strongly universal reversible counter machine U 109 with 10 counters, 109 states and 129 instructions. Now we will show how to bound the final value of non-output counters, i.e. obtain a garbage-less CM. We will use the construction from Theorem 2. This construction works as follows. Machine U 109 is run leaving the history in R8. Next the following copy procedure is executed transferring the resulting value from R0 to R10. This is done by copying the value of R0 to R9 and then copying it back from R9 to R0 and R10.

[q f , 9, Z, q c 1 ]

[q c 1 , 0, Z, q c 5 ] [q c 1 , 0, P, q c 2 ] [q c 2 , 0, -, q c 3 ]

[q c 3 , 9, +, q c 4 ] [q c 4 , 9, P, q c 1 ] [q c 5 , 9, Z, p f ] [q c 5 , 9, P, q c 6 ]

[q c 6 , 9, -, q c 7 ] [q c 7 , 0, +, q c 8 ] [q c 8 , 10, +, q c 9 ] [q c 9 , 0, P, q c 5 ]

Finally, the machine is run in a reverse manner (technically a copy of all rules with reverse operations should be provided, working on states where q replaced by p). This gives a total number of 109 × 2 + 9 = 227 states and 129 × 2 + 12 = 270 instructions.

Theorem 5. There exists a strongly universal garbage-less reversible counter machine U 227 with 11 counters, 227 states and 270 instructions.

Weak universality

Now consider the weakly universal machine U 31 (based on U 29 from [7]). Below we give the list of rules of this machine. In fact, the only modification in this machine with respect to U 31 concerns the simulation block, which is also depicted on Fig. 3. We remark that states q 25 , q 26 and q 29 are absent. Below we bold emphasized corresponding changes. q 1 q 16 q 18 q 23 q 20 q 28 q 27 q 30 q 31 q 32 q f 4P 4Z Fig. 3 Weakly universal counter machine U 31 .

We observe that there are only 3 incoming arcs to q 32 . In order to minimize the number of nodes and arcs we will construct a machine with at most 3 incoming arcs to each node. First add states q 33 and q 34 like in the case of U 36 , see Fig. 1. Next, consider a new state q 35 and add following rules: [q 33 , 6, P, q 35 ] [q 13 , 6, Z, q 35 ] [q 35 , 1, 0, q 34 ] We remark that on the branch yielding to q 33 the value of R6 is positive, because of the rule [q 13 , 6, P, q 14 ]. Hence, q 35 is reversible. Now we remark that in order to make reversible a state with at most three incoming arcs we can use a slightly modified version of the flowchart from Fig. 2. In fact, states q s 41 , q t 3 and q t 4 should be removed and the arrow leading to q t 3 should lead now to q t 5 . This allows to store the incoming arc number in the history, interpreted as a base-3 number.

Hence we showed how it is possible to construct a weak universal reversible counter machine. This machine has 97 states (33 + 6 + 2 × 15 + 2 × 14) and 116 instructions (44 + 6 + 2 × 17 + 2 × 16). Theorem 6. There exists a weakly universal reversible counter machine U 97 with 9 counters, 97 states and 116 instructions. Now we can use the construction from Theorem 3 to obtain a weakly universal reversible counter machine U with 2 counters. We refer to [10] for more details. In order to compute the parameters of U we recall that each jump instruction from U 97 is performed by one instruction in U, each plus or minus instruction of Ri is performed by p i + 10 instructions and p i + 7 new states (p i being the ith prime number). Each couple of zero and non-zero check on Ri instructions is performed by 3p i + 3 instructions using 2p i + 2 new states. A single zero check instruction is simulated using 3p i + 2 instructions and 2p i + 1 states, while a single non-zero check instruction is simulated using 2p i + 4 instructions and p i + 2 states. To minimize the number of instructions we will use a different sequence of prime numbers associated to counters (trying to use smaller primes for more frequently used counters).

The table below gives the number of instructions of each type in U 97 , as well as the chosen prime number. Theorem 7. There exists a weakly universal reversible counter machine U 1097 with 2 counters, 1097 states and 1568 instructions.

Conclusions

The table below summarizes the parameters of universal reversible counter machines constructed in this paper. We remark that as noted by [START_REF] Axelsen | What do reversible programs compute?[END_REF] there is no universal reversible counter machine in the strict sense, because any reversible machine computes an injective function and, obviously, the universal machine as defined above is not injective. In [START_REF] Axelsen | What do reversible programs compute?[END_REF]4] it is highlighted that corresponding constructions provide a machine for reversibly simulating any irreversible machine. Another solution provided in the paper above is to define the universal machine M as follows M (# M , x) = (# M , M (x)), i.e., the result of the computation of the universal machine on the pair consisting of the code of the simulated machine M and its input x is equal to the pair of the code of the simulated machine M and the result of its computation on the given input x. Since U 32 keeps a copy of the code of the simulated machine in R1, we can deduce that the simulations that we provide are universal in the above sense.

There are several possible directions for further research. One of them is the investigation of different trade-offs between the number of counters, states and instructions. It can be particularly interesting to see if as in [7] the increase of the number of counters can lead to the decrease of the number of instructions. Another interesting direction is the investigation of the universality type and independency for different number of counters.

Fig. 1

 1 Fig. 1 Strongly universal counter machine U 36 .


Jackson E Graves
email: jackson.graves@ens.psl.eu

Agathe Pralus

Lesly Fornoni

Andrew J Oxenham

Barbara Tillmann

Anne Caclin

Running head: CONSONANCE PERCEPTION IN CONGENITAL AMUSIA

Keywords: amusia, consonance, MMN, harmonicity, beating

Congenital amusia is a neurodevelopmental disorder characterized by difficulties in the perception and production of music, including the perception of consonance and dissonance, or the judgment of certain combinations of pitches as more pleasant than others. Two perceptual cues for dissonance are inharmonicity (the lack of a common fundamental frequency between components) and beating (amplitude fluctuations produced by close, interacting frequency components). Amusic individuals have previously been reported to be insensitive to inharmonicity, but to exhibit normal sensitivity to beats. In the present study, we measured adaptive discrimination thresholds in amusic participants and found elevated thresholds for both cues. We recorded EEG and measured the mismatch negativity (MMN) in evoked potentials to consonance and dissonance deviants in an oddball paradigm. The amplitude of the MMN response was similar overall for amusic and control participants; however, in controls there was a tendency towards larger MMNs for inharmonicity than for beating cues, whereas the opposite tendency was observed for the amusic participants. These findings suggest that initial encoding of consonance cues may be intact in amusia despite impaired behavioral performance, but that the relative weight of non-spectral (beating) cues may be increased for amusic individuals.

Consonance perception in congenital amusia: behavioral and brain responses to harmonicity and beating cues

INTRODUCTION

A fundamental aspect of Western tonal music is the phenomenon of consonance and dissonance, whereby certain combinations of simultaneous pitches are judged to be more pleasant, and to create less tension, than others. The perception of consonance and dissonance is determined at least in part by enculturation [START_REF] Butler | Musical consonance as musical preference: a crosscultural study[END_REF][START_REF] Lahdelma | Cultural familiarity and musical expertise impact the pleasantness of consonance/dissonance but not its perceived tension[END_REF][START_REF] Lundin | Toward a cultural theory of consonance[END_REF][START_REF] Mcdermott | Indifference to dissonance in native Amazonians reveals cultural variation in music perception[END_REF][START_REF] Popescu | The pleasantness of sensory dissonance is mediated by musical style and expertise[END_REF], but our ability to discriminate consonant from dissonant sounds is likely to reflect differences in the acoustic properties of those sounds. Listeners from Western cultures tend to rate pitch intervals with simple frequency ratios as more consonant than intervals with complex ratios, a phenomenon with at least two potential explanations. Dissonant (i.e., complex ratio) intervals generally produce beating: upper harmonics of the two tones can be close together in frequency and so interact in the auditory periphery, leading to amplitude fluctuations that are perceived as roughness, which is often described as unpleasant [START_REF] Hutchinson | The acoustic component of western consonance[END_REF][START_REF] Plomp | Tonal consonance and critical bandwidth[END_REF][START_REF] Von Helmholtz | On the Sensations of Tone as a Physiological Basis for the Theory of Music[END_REF]. Dissonant intervals also lack harmonicity: their components cannot be interpreted as multiples of a single common fundamental frequency [START_REF] Ebeling | Neuronal periodicity detection as a basis for the perception of consonance: A mathematical model of tonal fusion[END_REF][START_REF] Stumpf | Tonpsychologie[END_REF][START_REF] Terhardt | Pitch, consonance, and harmony[END_REF]. One study testing the relative importance of these two cues in young Western listeners found that inharmonicity was more likely than beating to underlie the perception of dissonance, particularly in those with some formal musical training [START_REF] Mcdermott | Individual differences reveal the basis of consonance[END_REF].

Further insight into consonance perception comes from the study of congenital amusia, a disorder characterized by difficulties in the perception and production of music in individuals with clinically normal hearing and no general cognitive deficits [START_REF] Ayotte | Congenital amusia: a group study of adults afflicted with a music-specific disorder[END_REF], which affects 2-4% of the population [START_REF] Kalmus | On tune deafness (dysmelodia): frequency, development, genetics and musical background[END_REF][START_REF] Peretz | Prevalence of congenital amusia[END_REF]. Deficits exhibited by individuals with amusia can provide insights about general mechanisms of music perception, and of auditory perception more generally. Pleasantness ratings of chords have been found to be impaired to some degree in congenital amusia, with control participants rating some chords (e.g., a perfect fifth) as more pleasant than others (e.g., an augmented fourth) and amusic participants showing less pronounced distinctions [START_REF] Cousineau | The basis of musical consonance as revealed by congenital amusia[END_REF][START_REF] Marin | Affective evaluation of simultaneous tone combinations in congenital amusia[END_REF]. One of these previous studies tested the perception of consonance and dissonance cues in amusic participants and found that they exhibited behavioral impairment for the detection of inharmonicity, but not for the detection of beating [START_REF] Cousineau | The basis of musical consonance as revealed by congenital amusia[END_REF], lending further support to the view that consonance perception is dominated by harmonicity, at least in Western musical cultures [START_REF] Mcdermott | Individual differences reveal the basis of consonance[END_REF].

Congenital amusia is generally thought of as a disorder affecting pitch perception [START_REF] Cousineau | Congenital amusia: a cognitive disorder limited to resolved harmonics and with no peripheral basis[END_REF][START_REF] Peretz | Neurobiology of congenital amusia[END_REF][START_REF] Tillmann | Congenital amusias[END_REF] and the perception of timbral cues relating to the frequency content of sounds [START_REF] Graves | Shortand long-term memory for pitch and non-pitch contours : Insights from congenital amusia[END_REF][START_REF] Marin | Perception of musical timbre in congenital amusia: Categorization, discrimination and short-term memory[END_REF], leaving intact other capabilities, such as memory for speech stimuli (Albouy, Peretz, et al., 2019;[START_REF] Tillmann | Congenital amusia: A short-term memory deficit for non-verbal, but not verbal sounds[END_REF], and with more restricted or conditional deficits for other musical attributes, like rhythm [START_REF] Foxton | Rhythm deficits in "tone deafness[END_REF][START_REF] Hyde | Brains that are out of tune but in time[END_REF] and loudness [START_REF] Graves | Shortand long-term memory for pitch and non-pitch contours : Insights from congenital amusia[END_REF][START_REF] Tillmann | Impaired short-term memory for pitch in congenital amusia[END_REF]. However, a recent study [START_REF] Whiteford | Auditory deficits in amusia extend beyond poor pitch perception[END_REF] found that amusic individuals were also impaired at detecting amplitude modulation (AM) as well as frequency modulation (FM), suggesting that the deficit may not be limited to cues related to pitch and timbre. The finding that amusics are impaired at AM detection has interesting implications for amusic perception of beating, and seems to conflict with the previously reported lack of amusic impairment for beating perception [START_REF] Cousineau | The basis of musical consonance as revealed by congenital amusia[END_REF]. This discrepancy may be due to the different levels of AM tested by the two studies: [START_REF] Cousineau | The basis of musical consonance as revealed by congenital amusia[END_REF] used stimuli that produced the equivalent of 100% depth of AM (well above threshold), whereas [START_REF] Whiteford | Auditory deficits in amusia extend beyond poor pitch perception[END_REF] measured pure-tone AM detection abilities at modulation depths near detection threshold. However, thresholds for the detection of beating in a complex tone have not been directly measured for amusic individuals, and further exploration of consonance perception in amusia is warranted to resolve this apparent discrepancy.

Studies of brain function and anatomy in amusia generally point to an origin of the deficit in the network connecting auditory areas in temporal cortex with higher-level areas in frontal cortex [START_REF] Albouy | Impaired pitch perception and memory in congenital amusia: The deficit starts in the auditory cortex[END_REF][START_REF] Albouy | Altered retrieval of melodic information in congenital amusia : insights from dynamic causal modeling of MEG data[END_REF][START_REF] Hyde | Morphometry of the amusic brain : a two-site study[END_REF][START_REF] Hyde | Cortical thickness in congenital amusia: when less is better than more[END_REF][START_REF] Hyde | Functional MRI evidence of an abnormal neural network for pitch processing in congenital amusia[END_REF][START_REF] Leveque | Altered intrinsic connectivity of the auditory cortex in congenital amusia[END_REF]. In terms of early cortical encoding of pitch, fMRI studies have not observed differences in amusics' activation patterns with classical subtraction analyses [START_REF] Hyde | Functional MRI evidence of an abnormal neural network for pitch processing in congenital amusia[END_REF][START_REF] Norman-Haignere | Pitch-responsive cortical regions in congenital amusia[END_REF]. However, a re-analysis with whole-brain multivariate pattern analyses revealed that amusic and control participants differed in their pattern of functional activity in right Heschl's gyrus (Albouy, Caclin, et al., 2019). In addition, an MEG study observed differences in amusics and controls at the early level of the N100m response [START_REF] Albouy | Impaired pitch perception and memory in congenital amusia: The deficit starts in the auditory cortex[END_REF], leaving open the possibility that early pitch processing may also be affected in amusia.

Automatic sound processing in amusia has previously been studied using the mismatch negativity (MMN), an EEG potential recorded in response to sounds that violate low-level auditory expectations, and that can occur even in the absence of directed attention [START_REF] Näätänen | Early selective-attention effect on evoked potential reinterpreted[END_REF][START_REF] Näätänen | The mismatch negativity (MMN) in basic research of central auditory processing: A review[END_REF]. Despite showing behavioral impairment at pitch discrimination tasks, amusic individuals have been found to exhibit normal MMN responses, even to small pitch changes that are below their behavioral discrimination threshold [START_REF] Moreau | Automatic brain responses to pitch changes in congenital amusia[END_REF][START_REF] Moreau | Pitch discrimination without awareness in congenital amusia: Evidence from event-related potentials[END_REF][START_REF] Peretz | The amusic brain: In tune, out of key, and unaware[END_REF]. A similar pattern of overall normal MMNs in amusia has also recently been observed for emotional prosody [START_REF] Pralus | Pre-attentive processing of neutral and emotional sounds in congenital amusia[END_REF] and in pitch sequences of various levels of melodic complexity [START_REF] Quiroga-Martinez | Listeners with congenital amusia are sensitive to context uncertainty in melodic sequences[END_REF]), yet with differences in an early negativity preceding the MMN as well as in the P3a [START_REF] Pralus | Pre-attentive processing of neutral and emotional sounds in congenital amusia[END_REF]. One EEG study found a reduced early frontal negativity in response to unpredictable notes in a melody [START_REF] Omigie | Electrophysiological correlates of melodic processing in congenital amusia[END_REF], suggesting that potential impairments of automatic brain responses at this early level may still exist for amusics for certain perceptual cues.

For normal-hearing, non-amusic listeners, the MMN has also been reported in response to harmonicity changes and to pitch differences of harmonic complex tones [START_REF] Butler | Sequencing the cortical processing of pitch-evoking stimuli using EEG analysis and source estimation[END_REF][START_REF] Tervaniemi | Effects of spectral complexity and sound duration on automatic complex-sound pitch processing in humans -A mismatch negativity study[END_REF]. In addition to high-level cues like tonal expectation [START_REF] Marmel | Tonal expectations influence early pitch processing[END_REF], the MMN has been observed in response to differences in consonance and dissonance [START_REF] Brattico | Neural discrimination of nonprototypical chords in music experts and laymen: An MEG study[END_REF][START_REF] Crespo-Bojorque | Early neural responses underlie advantages for consonance over dissonance[END_REF][START_REF] Linnavalli | Musical expertise facilitates dissonance detection on behavioral, not on early sensory level[END_REF]. More specifically, an MMN has been measured in response to inharmonicity in the form of a mistuned harmonic (Alain et al., 2001), to harmonicity in the form of a harmonic complex presented in the context of inharmonic complexes [START_REF] Jones | Sensitivity of human auditory evoked potentials to the harmonicity of complex tones: Evidence for dissociated cortical processes of spectral and periodicity analysis[END_REF], and to roughness cues created by beating-induced AM [START_REF] De Baene | Roughness perception in sounds: Behavioral and ERP evidence[END_REF]. The MMN may therefore be a good candidate for indexing early neural processing of consonance and dissonance in amusia, as its presence has been established in response to pitch changes for amusic participants, and in response to dissonance cues for normal-hearing listeners.

In the present study, we measured behavioral sensitivity and MMN for amusic and control participants to two potential cues for consonance and dissonance: inharmonicity (harmonic complex tones vs. linearly shifted harmonics, resulting in an inharmonic series) and beating (inharmonic complex tones with or without spectral sideband components added to produce beats). In the first experiment, participants' detection thresholds were measured for both inharmonicity and beating cues, as well as for pure-tone AM to assess basic sensitivity to amplitude fluctuations [START_REF] Whiteford | Auditory deficits in amusia extend beyond poor pitch perception[END_REF]. In the second experiment, participants listened either actively or passively to streams of stimuli in an oddball paradigm, where a dissonant stimulus deviated from a standard consonant stimulus, or vice versa. If behavioral impairments for consonance perception in amusia [START_REF] Cousineau | The basis of musical consonance as revealed by congenital amusia[END_REF][START_REF] Marin | Affective evaluation of simultaneous tone combinations in congenital amusia[END_REF] can be traced to differences in early encoding of these cues, this could be reflected in reduced MMN amplitude for amusic individuals. If, on the other hand, the deficits arise from later processes, amusic individuals should show normal MMN responses to these stimuli.

EXPERIMENT 1: BEHAVIORAL DISCRIMINATION

Methods

Participants

Amusia is rare in the general population [START_REF] Peretz | Prevalence of congenital amusia[END_REF], making recruitment challenging. However, the effect sizes for relevant behavioral measures, such as pitch discrimination or inharmonicity detection (e.g. [START_REF] Cousineau | The basis of musical consonance as revealed by congenital amusia[END_REF], have been very large when comparing amusic and control groups. For instance, the partial eta-squared (η p 2 ) values for pitch discrimination thresholds reported by [START_REF] Whiteford | Auditory deficits in amusia extend beyond poor pitch perception[END_REF] were greater than 0.3, more than twice the value generally considered a large effect size (η p 2 = 0.14 ;[START_REF] Cohen | Statistical power analysis for the behavioral sciences[END_REF].

Assuming an effect size of η p 2 = 0.14 for a within-between interaction effect in an ANOVA, the sample size required to detect this effect with 80% power is only 8 participants per group.

Similarly, for inharmonicity detection, an examination of the individual data reported by [START_REF] Cousineau | The basis of musical consonance as revealed by congenital amusia[END_REF]their Fig. 6) suggests a Cohen's d value of 3.28, which is more than four times the value generally considered a large effect (d = 0.8; [START_REF] Cohen | Statistical power analysis for the behavioral sciences[END_REF]. Assuming an effect size of at least d = 1.5 in the current study, the sample size required to detect this effect with 80% power is only 9 participants per group. Most previous behavioral studies of amusia have recruited at least 10-15 participants per group (e.g. [START_REF] Cousineau | The basis of musical consonance as revealed by congenital amusia[END_REF][START_REF] Whiteford | Auditory deficits in amusia extend beyond poor pitch perception[END_REF]. We therefore recruited 12 amusic individuals (6 female and 6 male) and 11 control participants (7 female and 4 male) for our study measuring behavioral thresholds.

During recruitment, control participants were matched to amusic participants in terms of age, education, gender, and handedness (see Table 1). No participants had any formal musical training, except for one control participant who reported one year of musical training. All participants had normal hearing as determined by pure tone audiometry, and congenital amusia was identified with the Montreal Battery of Evaluation of Amusia (MBEA) [START_REF] Peretz | Varieties of musical disorders: The Montreal Battery of Evaluation of Amusia[END_REF].

Following the MBEA, each participant's frequency difference limen (FDL) was also measured using the adaptive tracking procedure described in [START_REF] Peretz | Varieties of musical disorders: The Montreal Battery of Evaluation of Amusia[END_REF]. MBEA scores for the pitch-related subtests only (Scale, Interval, and Contour) are also listed, along with frequency difference limens (FDL) measured using an adaptive tracking procedure [START_REF] Tillmann | Congenital amusia: A short-term memory deficit for non-verbal, but not verbal sounds[END_REF].

Stimuli

Complex tones, inspired by the stimuli of [START_REF] Cousineau | The basis of musical consonance as revealed by congenital amusia[END_REF], were generated in four categories to manipulate consonance cues: harmonic, inharmonic, no-beating, and beating (see Figure 1). Harmonic complexes consisted of the 1 st , 2 nd , 3 rd , 5 th , and 9 th components of a harmonic series, added together in sine phase. Inharmonic complexes were generated by shifting every component in the harmonic complex up by a uniform distance in linear frequency. When manipulating beating cues, we wanted to be sure that the perception of dissonance was not due to inharmonicity from the introduction of non-harmonic components, but purely due to beating. The stimuli were therefore always inharmonic, with frequency components chosen by sampling from a uniform distribution between -30 and +30 Hz relative to each component in the equivalent harmonic stimulus, added together in random phase. Beating stimuli were created by adding a single sideband component 30 Hz away from each component, with a uniform level difference between sidebands and original components. The location of sidebands (above or below original components) was randomly chosen for each complex but was consistent within the complex. See supplemental audio files SA1 -SA4 for examples of complexes in each of the four categories b .

b Suppplemental material can be found at: https://osf.io/zmeaq/ In addition to our manipulation of beating, which introduced AM to a complex tone, we also directly measured thresholds for detection of pure-tone sinusoidal AM. Stimuli for the AM detection test involved a pure-tone carrier with a frequency that was roved between 277 and 370

Hz. When AM was present, the modulation frequency was constant at 10 Hz. This was chosen to be at an intermediate frequency from the ones tested by [START_REF] Whiteford | Auditory deficits in amusia extend beyond poor pitch perception[END_REF] of 4 and 20 Hz. Sinusoidal AM (SAM) detection differs from beat detection because SAM involves two symmetrical placed spectral sidebands, whereas beat detection involves only one; however, SAM and beat thresholds are closely related and are independent of modulation rate between 10 and 30

Hz [START_REF] Kohlrausch | The influence of carrier level and frequency on modulation and beat-detection thresholds for sinusoidal carriers[END_REF].

To ensure that the perception of dissonance cues was based on the dissonance itself and not on a perceived difference in pitch, we randomly varied the fundamental frequency (F0)

between intervals of all tones used in both experiments. The F0 of each complex tone (or carrier frequency for AM stimuli, or nominal F0 for all inharmonic complex tones) was chosen from among six discrete values, at semitone increments between C#4 (277 Hz) and F#4 (370 Hz). F0s

were chosen such that throughout both experiments, no two consecutive tones shared the same F0, including both standard and deviant tones. All complex tones had a decaying spectral envelope, such that components decreased in level at a rate of 14 dB/octave from the lowest frequency component. The duration of each tone was 500 ms, including 10-ms raised-cosine onset and offset ramps, and the overall level of each tone was 65 dB sound pressure level (SPL).

All stimuli were created using MATLAB (The Mathworks, Natick, MA) and presented diotically at a sampling rate of 48 kHz through circumaural Sennheiser HD 280 pro headphones in a quiet sound booth.

Procedure

Participants discriminated inharmonic from harmonic, beating from no-beating, or AM from no-AM stimuli in a 3AFC task. On each trial, participants heard three tones, and were asked to select the tone that sounded different from the other two. The target tone was always the more dissonant sound (inharmonic, beating, or AM), while the two reference tones were more consonant (harmonic, no beating, or no AM). The size of the spectral shift for inharmonic stimuli and the amplitudes of the sidebands for beating stimuli were adaptively varied in order to measure threshold. During this adaptive procedure, the size of the inharmonic frequency shift varied on a logarithmic scale between 1 and 125 Hz and the amplitude of the sidebands varied between -60 and 0 dB relative to the original components. Listeners were instructed to ignore the random changes in F0 and to identify the tone that stood out from the other two (without explaining explicitly on which feature). Feedback on whether the response was correct or incorrect was provided immediately after each trial.

The difference between target and reference was adaptively varied, and discrimination thresholds were measured using a tracking procedure following a 2-down 1-up rule that tracks the 70.7% point on the psychometric function [START_REF] Levitt | Transformed up-down methods in psychoacoustics[END_REF]). An adaptive run began at 50 Hz and changed by factors of 2.51, 1.58, and 1.26 (inharmonic shift) or began at -10 dB and changed by step sizes of 4, 2, and 1 dB (sideband and AM depth). The step size changed every two reversals until the final step size, after which the run continued for a further six reversals at the final step size. Each participant completed three runs for each cue (harmonicity, beating, and AM) and the values at the six last reversals from each run were averaged (geometric means for inharmonicity) for an estimated threshold. The order of conditions was partially counterbalanced, with half of participants performing the tasks in the order of harmonicity, AM, and beating, and the other half performing the tasks in the order of AM, beating, and harmonicity. Each condition was preceded by a brief orientation period, consisting of three labeled example trials with large differences equal to the starting value.

Results

Inharmonic shift thresholds were larger for amusic participants than for control participants [t(1,21) = 2.24, p = 0.036, d = 0.94] (see Figure 2A). A similar effect was observed for both of the beating-related tasks: complex single-sideband beating detection [t(1,21) = 2.91, p = 0.0084, d = 1.23] (Figure 2B) and pure-tone SAM detection [t(1,21) = 2.98, p = 0.0071, d = 1.27] (Figure S1). Although the deficits associated with amusia are often considered to be pitch specific, here amusic participants exhibited reduced behavioral sensitivity to non-pitch cues in beating and pure-tone SAM detection. The similar effect sizes suggest that the deficit in detecting beating may be as large under amusia as the deficit in detecting inharmonicity. As expected, detection of beating in a complex tone was comparable to detection of pure-tone SAM.

In addition, thresholds for these two tasks correlated with each other [r = 0.73, p < 0.001], and

EXPERIMENT 2: EEG MEASUREMENT OF THE MISMATCH NEGATIVITY

Methods

Participants

Most previous EEG studies of amusia have recruited 10-20 participants per group (e.g. [START_REF] Moreau | Pitch discrimination without awareness in congenital amusia: Evidence from event-related potentials[END_REF][START_REF] Quiroga-Martinez | Listeners with congenital amusia are sensitive to context uncertainty in melodic sequences[END_REF], so for our EEG study, we recruited 19 amusic individuals (10 female and 9 male) and 21 control participants (13 female and 8 male).

Out of the participants in Experiment 2, 13 individuals (5 amusics and 8 controls) had also participated in Experiment 1. Participants in Experiment 2 took part in two consecutive MMN studies within the same session; the first one with emotional vowels is reported in Pralus et al.

(2020) and the second one is reported here.

Controls

Stimuli

All tones used in Experiment 2 were generated according to the same rules as in Experiment 1, in one of four types: harmonic, inharmonic, no-beating or beating (see Figure 1 and Experiment 1 stimuli). For Experiment 2, a constant shift size and sideband amplitude were chosen to differentiate the standard and deviant stimuli to be played to every participant. These levels were chosen to maximize the difference in discriminability between participant groups (amusic and control) observed in Experiment 1. Accordingly, we chose an inharmonic shift of 12 Hz, which was above threshold for 82% of control participants, but was above threshold for only 42% of amusic participants, and a sideband amplitude of -19 dB (relative to the original tones), which was above threshold for 82% of control participants, but was above threshold for only

Procedure

During EEG recording, streams of tones were presented to participants with a stimulus onset asynchrony (SOA) of 700 ms. In each of four conditions, one stimulus type was defined as standard, occurring on 5/6 of trials, and its opposite as deviant, occurring on only 1/6 of trials (see Figure 3). Conditions were named after the deviant tone: harmonic-deviant (HDEV), inharmonic-deviant (IDEV), no-beating-deviant (NDEV), and beating-deviant (BDEV). Deviants were always separated from each other in the stream by no more than 7 and no fewer than 3 standards. The F0 of each tone was selected randomly, with the constraint that no two consecutive tones shared the same F0. Each participant completed four blocks of passive listening followed by four blocks of an active task (see below). Passive blocks always came before active blocks. The order of the four blocks was always the same in passive and active phases, but the order of blocks was counterbalanced across participants. Passive blocks contained 140 deviants and 700 standards in total, and participants were instructed to sit still and watch a silent subtitled movie. Active blocks contained 30 deviants and 150 standards, and participants were instructed to press a button every time they heard a sound that was different from most other sounds.

As a measure of behavioral sensitivity to the difference between standard and deviant, the sensitivity index d was calculated from active-task responses in the following manner: Any responses between 100 and 2200 ms after a deviant onset were counted as a hit for that deviant, and any responses between 2200 ms after one deviant onset and 100 ms after the following deviant onset were counted as a false alarm. In this way, the duration of hit periods was constant at 2100 ms per deviant, while the duration of false alarm periods was variable from 700 to 3500 ms, but averaged 2100 ms, meaning that a random responder would make roughly equal numbers of hits and false alarms. The value of d was then calculated using the resulting hit and false alarm rates [START_REF] Stanislaw | Calculation of signal detection theory measures[END_REF].

EEG recording and preprocessing

EEG was recorded from 31 Ag/AgCl active electrodes (Acticap, Brain Products GmbH, Gilching, Germany), with a nose reference, at a sampling rate of 1000 Hz with a 0.016-1000 Hz bandwidth (BrainAmp Standard Amplifier, Brain Products GmbH, Gilching, Germany). Vertical eye movements were recorded with an additional active electrode positioned under the left eye (offline re-referenced to Fp1). Pre-processing was conducted in MATLAB using functions from eeglab [START_REF] Delorme | EEGLAB: an open source toolbox for analysis of single-trial EEG dynamics including independent component analysis[END_REF]. Data was bandstop filtered to remove line noise, using 4 thorder Butterworth filters with cutoffs of 47 and 53 Hz, then 147 and 153 Hz. A 20-s portion of data containing eyeblinks but few other artifacts was visually selected for each participant, for the purpose of performing an independent components analysis (ICA). ICA weights from this subset of data were visually examined, eyeblink components were selected and then removed from the entirety of the data through an ICA inverse transformation. After ICA-based blink correction, the data were divided into 700-ms epochs, from -200 ms to +500 ms relative to stimulus onset, and non-blink artifacts were rejected using a dynamic range threshold applied to each epoch. This threshold, and the channels to be ignored for artifact rejection, were manually selected for each participant based on visual inspection of the data (thresholds were constant across channels for each participant, and ranged from 90 µV to 300 µV, with an average of 153 µV; the number of excluded channels ranged from 0 to 21, with an average of 7.59). Of the 140

Figure 3. Oddball paradigm with consonance changes and pitch roving. Participants heard deviant (red) and standard (blue) stimuli in four different experimental conditions, while nominal F0 varied constantly, with a minimum distance of one semitone between each pair of two consecutive tones. Each of the four stimulus types (harmonic, inharmonic, nobeating and beating) served as the deviant in one condition, with its contrast serving as the standard. Left panels: sound spectra for inharmonic-deviant (A) and harmonic-deviant (B) conditions; dashed grey lines indicate harmonic partials. Right panels: sound waveforms for beating-deviant (C) and no-beating-deviant (D) conditions, plotted at the level of their fundamental frequency (F0). In the beating-deviant and no-beating-deviant conditions, all sounds were inharmonic.

deviant trials in each passive block, the average number rejected due to artifacts was 31, leaving an average of 109 deviants for analysis per passive block. After artifact rejection, epochs were averaged for each condition, separately for deviants and standards, excluding standards immediately following a deviant. The resulting ERPs were bandpass filtered (Butterworth, 4 th order) from 2 to 30 Hz, and the baseline from 100 ms to 0ms before stimulus onset was subtracted. Finally, any exceptionally noisy electrodes were removed and re-interpolated from surrounding electrodes based on their three-dimensional coordinates.

Analysis of EEG data

Only EEG data from the passive listening blocks were analyzed. The MMN was evaluated by subtracting ERPs to standard sounds from their acoustically identical deviant sounds. This means, for example, that the harmonic deviant (from the HDEV block) was compared against the harmonic standard (from the IDEV block), not against the (inharmonic) standard from its own block. In this way, any measured difference between ERPs cannot be due to acoustic differences between the sounds, as they are the same sound, and is likely instead to arise from neural encoding of the deviant sound as deviant. For each deviant-standard pair, ERP amplitudes were evaluated for the whole brain over pre-defined periods of interest to assess whether significant MMN and/or P3a emerge (see below). Spatiotemporal clusters of significant differences between standard and deviant ERP amplitudes over each period were identified using non-parametric cluster-based permutation statistics [START_REF] Blair | An alternative method for significance testing of waveform difference potentials[END_REF], implemented with the Fieldtrip toolbox in MATLAB [START_REF] Maris | Nonparametric statistical testing of EEG-and MEG-data[END_REF]. Using this method, contiguous spatiotemporal clusters of differences between standard and deviant were identified, and the significance of a cluster was determined by comparing the sum of t-values in this cluster to the sum of t-values in the largest cluster identified when standard and deviant labels were randomly permuted for each subject over 10,000 iterations. The associated cluster-level p-value was the proportion of random permutations that resulted in a cluster larger than the one identified.

We used cluster-based permutation statistics to identify electrode sites and temporal windows where a significant MMN emerged (defined for our study as a negativity within the 150-300 ms time range) or where a significant P3a emerged (for our study, a positivity in the 300-450 ms time range). These clusters were identified across all participants, separately for each of the four deviant types (harmonic, inharmonic, no-beating, and beating). The difference values (deviant minus standard) within each spatiotemporal cluster were then averaged together for comparison by group (amusic or control), feature (beating or harmonicity) and consonance (consonant or dissonant).

Results

Decreased behavioral sensitivity to harmonicity and beating changes in amusia

When tested behaviorally during the active task blocks of Experiment 2, deviant detection was impaired in amusic participants for both cues (see Figure 4). We conducted a nonparametric c version of a 3-way mixed ANOVA on sensitivity (d) considering the betweensubjects factor of participant group (amusic or control) and within-subjects factors of feature (harmonicity or beating) and consonance (consonant vs. dissonant deviants), using the nparLD package in R [START_REF] Noguchi | nparLD : An R Software Package for the Nonparametric Analysis of Longitudinal Data in Factorial Experiments[END_REF]. We found a main effect of consonance [F(1,38) = 10.61, p = 0.0011, η p 2 = 0.32], reflecting better performance on dissonant-deviant blocks (IDEV and BDEV, as measured adaptively in Experiment 1) than on consonant-deviant blocks (HDEV and NDEV). We also found a main effect of participant group [F(1,38) = 4.74, p = 0.029, η p 2 = 0.09], reflecting better performance for the control than the amusic group. No other significant main effects or interactions were found (all p > 0.35).

c Because d is not normally distributed, with a mode at 0 (representing chance performance), but a longer positive tail (representing better-than-chance performance), a nonparametric test is more appropriate.

Some participants had previously participated in the threshold measurement study, in which the 3AFC task with its dissonant target resembled the dissonant-deviant conditions more than the consonant-deviant conditions. In order to test whether the apparent effect of consonance was merely an effect of practice from Experiment 1, we re-ran the ANOVA excluding the 13 participants who had completed Experiment 1. The main effect of consonance remained after removing these subjects [F(1,25) = 5.09, p = 0.024, η p 2 = 0.27], suggesting that this effect was not due to participants having practiced, and may reflect an inherent perceptual asymmetry in the stimuli, perhaps due to processes of auditory feature extraction [START_REF] Cusack | Perceptual asymmetries in audition[END_REF].

Participant performance was evaluated against chance with Wilcoxon signed rank tests of d against zero. Control participants performed significantly better than chance in all four conditions (IDEV: p = 0.0034, HDEV: p = 0.011, BDEV: p = 0.0065, NDEV: p = 0.016), while amusic participants only performed better than chance in the IDEV condition (p = 0.048) and the BDEV condition (p = 0.036). If Bonferroni multiple-comparisons correction was applied (α = 0.05 / 8 = 0.00625), only control participants performed better than chance, and only in the IDEV condition. These results, along with the significant main effect of group on d, suggest that behavioral discrimination of the stimuli used in the EEG study was more difficult for the amusic than for the control group, as expected based on the results from Experiment 1.

Presence of the MMN and P3a in response to consonant sounds

Each deviant ERP was compared against its acoustically identical standard (see Figure 5).

In general, peak negativity of deviants relative to standards occurred in frontal electrodes between 150 and 300 ms, followed by positivity in frontal electrodes between 300 and 450 ms (see Figures 6 andS2). Significant MMNs were observed only for conditions HDEV and NDEV.

Across all participants, significant MMN clusters were identified for harmonic deviants compared to harmonic standards (p = 0.034, 150-290 ms) and no-beating deviants compared to no-beating standards (p = 0.011, 150-300 ms), but not for inharmonic or beating stimuli (cluster- level p > 0.73). See Figure S3 for the temporal course of MMN topographies. A significant P3a

cluster was identified for harmonic stimuli (p = 0.026, 300-440 ms), but not for the other three sounds (cluster-level p > 0.48).

Amplitude of the MMN by consonance, group, and feature

We compared the amplitude of ERPs across participant groups, features, and consonance levels by running a 3-way mixed ANOVA on MMN magnitudes, considering the factors of consonance (consonant vs. dissonant deviant), feature (beating vs. inharmonicity), and group (amusic vs. control). It is important to note that conditions in this ANOVA differed from each other based on the contrast between deviant and standard, and not based on the deviant or standard alone. MMNs were averaged within the relevant spatiotemporal cluster: for harmonic and inharmonic stimuli, the harmonic MMN cluster; for no-beating and beating stimuli, the no- beating MMN cluster (see Figure 7). We observed a main effect of consonance on MMN amplitude [F(1,38) = 15.13, p < 0.001, η p 2 = 0.28], reflecting larger MMNs for harmonic and nobeating stimuli than for inharmonic and beating stimuli, in keeping with the fact that the presence of the MMN was only confirmed in the HDEV and NDEV conditions (see section 3.2.2). This effect ran opposite to the effect of consonance on behavior, as stronger MMNs were observed in response to consonant deviants, but better behavioral performance was found for dissonant deviants. As with the behavioral results, we re-ran this analysis without the 13 subjects who had completed Experiment 1, in order to check whether it might be related to practice on the 3AFC threshold task with dissonant targets. After removing these subjects, the effect of consonance on MMN strength persisted [F(1,25) = 13.18, p = 0.0013, η p 2 = 0.35], suggesting it did not depend on practice in the threshold task.

We also observed an interaction between group (amusic vs. control) and feature (beating vs. harmonicity) [F(1,38) = 4.24, p = 0.046, η p 2 = 0.10]. The direction of the interaction (see Figure 7) suggests that MMNs in the control group were larger for harmonicity cues (HDEV and IDEV) than for beating cues (NDEV and BDEV), but MMNs in the amusic group were larger for beating than harmonicity. However, post-hoc between-group comparisons (independent t-tests)

showed no significant differences between the amusic and control groups for harmonicity cues shows mean MMN amplitude, averaged within the relevant spatiotemporal cluster for each group and condition. Error bars show ±1 SEM. For harmonic and no-beating stimuli, averages were computed in the cluster for that stimulus across both groups. As no significant clusters were identified for dissonant stimuli, inharmonic and beating stimuli borrowed the clusters for harmonic and no-beating stimuli, respectively. (F) is as (E), but for P3a amplitude, with other sounds borrowing the cluster for harmonic stimuli.

differences between MMN amplitude to harmonicity and beating cues in either the amusic [t(1,18) = -1.68, p = 0.11] or control [t(1,20) = 1.17, p = 0.25] groups . The interaction was not significant if the 13 participants who completed Experiment 1 were removed [F(1,25) = 3.16, p = 0.088, η p 2 = 0.11], nor when the analysis was restricted to include only consonant-deviant conditions, where significant MMNs were observed [F(1,38) = 1.78, p = 0.19, η p 2 = 0.06].

No other significant main effects or interactions were identified in the ANOVA, regardless of whether the 13 participants who completed Experiment 1 were removed (all p > 0.57). The notable lack of main effect of group means that we found no evidence for reduced MMNs to consonance cues in amusic individuals overall. This neurophysiological outcome is in contrast to our behavioral results, where amusics were impaired overall for both cues, both in terms of threshold and sensitivity.

In order to confirm the presence of an MMN for each group in each condition, we compared averaged MMN strengths against zero using one-tailed t-tests, since the expected direction of the effect is negative. Only three MMNs were significant using this test: of controls to harmonic stimuli [t(1,20) = -3.06, p = 0.0031], of controls to no-beating stimuli [t(1,20) = -1.86, p = 0.039], and of amusics to no-beating stimuli: [t(1,18) = -2.13, p = 0.024]. These results, combined with the observed interaction effect, suggest a comparative advantage, in terms of early brain responses, for harmonicity cues for controls and beating cues for amusics.

To evaluate P3a amplitudes across group and condition, we ran a 3-way mixed ANOVA on ERP amplitudes in the P3a cluster identified for harmonic stimuli. No main effects or interactions were observed (all p > 0.12). Limiting the analysis to harmonic stimuli where a P3a response was observed, we observed no significant difference in P3a amplitude between amusic and control groups [t(1,38) = 0.09, p = 0.93]. To verify the presence of a P3a response for each group in each condition, we compared averaged P3a strengths against zero using one-tailed ttests. Only the P3a responses to harmonic stimuli were significant, for both controls [t(1,20) = 2.16, p = 0.022], and amusics [t(1,18) = 1.77, p = 0.047].

DISCUSSION

In our study, amusic participants showed an impaired ability to discriminate dissonant from consonant sounds, whether using beating or inharmonicity cues. Their MMN responses to the same stimuli were of similar amplitude to those of controls, although they showed a comparatively stronger MMN to beating cues than to inharmonicity cues, relative to controls.

These findings have implications for understanding congenital amusia, as well as for the processing of consonance and dissonance overall.

Processing of harmonicity and beating in congenital amusia

We observed that amusic individuals have elevated thresholds (Experiment 1) and decreased behavioral sensitivity (Experiment 2) for detection of beating as well as of inharmonicity. Although amusics are behaviorally less sensitive to both beating and harmonicity cues, we found that their MMN responses to these cues were of comparable overall strength to control participants. This finding suggests that initial encoding of these dissonance cues may be intact in amusics despite their poor behavioral performance, pointing to higher-level mechanisms as the source for behavioral impairment. Our results thus agree with previous research suggesting that amusia-related impairments originate in a frontotemporal network connecting auditory areas to higher-order areas involved in working memory and conscious judgments [START_REF] Albouy | Impaired pitch perception and memory in congenital amusia: The deficit starts in the auditory cortex[END_REF][START_REF] Albouy | Altered retrieval of melodic information in congenital amusia : insights from dynamic causal modeling of MEG data[END_REF][START_REF] Hyde | Morphometry of the amusic brain : a two-site study[END_REF][START_REF] Hyde | Cortical thickness in congenital amusia: when less is better than more[END_REF][START_REF] Hyde | Functional MRI evidence of an abnormal neural network for pitch processing in congenital amusia[END_REF][START_REF] Leveque | Altered intrinsic connectivity of the auditory cortex in congenital amusia[END_REF].

Our general finding of behavioral impairment for the perception of consonance in amusia agrees with previous studies [START_REF] Cousineau | The basis of musical consonance as revealed by congenital amusia[END_REF][START_REF] Marin | Affective evaluation of simultaneous tone combinations in congenital amusia[END_REF] that used different methods and stimuli to address a similar question. In these studies, participants gave subjective pleasantness ratings in response to more ecologically valid musical stimuli. These stimuli have the advantage of being directly relevant to the real-world experience of music by people with amusia: we can directly conclude that they do not perceive consonance in the same way as control participants. In the present study, as well as in Experiments 3 and 4 of [START_REF] Cousineau | The basis of musical consonance as revealed by congenital amusia[END_REF], participants were instead tested with objective discrimination tasks, using more well controlled, but highly artificial, lab-synthesized stimuli. On the general question of impairment for consonance/dissonance sensitivity in amusia, the present study agrees with these past studies.

Contrary to the conclusions of [START_REF] Cousineau | The basis of musical consonance as revealed by congenital amusia[END_REF], however, our findings suggest that congenital amusia involves deficits in the perception of beating as well as the perception of harmonicity. The difference between the previous and present studies likely arises from the fact that the present study tested participants at low modulation depths, at and near threshold, as opposed to using high modulation depths that were easily detectable for both groups (as in [START_REF] Cousineau | The basis of musical consonance as revealed by congenital amusia[END_REF]. Our finding of behavioral impairment for beating detection (and closely related AM detection) replicates a recent finding that amusic individuals exhibit deficits for AM as well as FM coding [START_REF] Whiteford | Auditory deficits in amusia extend beyond poor pitch perception[END_REF], also using threshold measurements.

Nevertheless, the interaction effect we observed in MMN amplitudes suggests that amusics' encoding of beating may be stronger relative to harmonicity, compared to controls.

Although this interaction was not significant when analyses were limited to conditions with significantly negative MMNs, the tendency remains and is supported by the finding of a significant MMN to harmonic sounds for controls, but not for amusics. This interaction may in theory reflect either impaired harmonic encoding or enhanced AM encoding in amusia. Given the behavioral results, both here and in a previous study [START_REF] Whiteford | Auditory deficits in amusia extend beyond poor pitch perception[END_REF], suggesting that amusia is related to impairments in both inharmonicity and beat detection, the theory of impaired harmonic perception in amusia seems more plausible. Nevertheless, despite these behavioral deficits, our EEG findings suggest that amusics are, at a minimum, not significantly impaired for early processing of AM in the form of beating cues. It might be argued that the increased representation of beating cues in the MMN of amusic individuals could be a primary, congenital difference in brain function of amusic individuals. But perhaps more likely, it may be a secondary result of impoverished spectral information, in which amusics develop relatively heightened representations of early information from sources that remain available.

This phenomenon may also explain why amusic individuals remain able to use acoustic cues, such as loudness [START_REF] Graves | Shortand long-term memory for pitch and non-pitch contours : Insights from congenital amusia[END_REF] or non-spectral cues for prosody [START_REF] Pralus | Emotional prosody in congenital amusia: Impaired and spared processes[END_REF].

Under this explanation, the increased emphasis on beating cues could be compared to some examples of enhanced visual perception for people with profound hearing loss (e.g. [START_REF] Bernstein | Speech perception without hearing[END_REF][START_REF] Bottari | Changes in early cortical visual processing predict enhanced reactivity in deaf individuals[END_REF], or to enhanced auditory perception for people with low vision (e.g. [START_REF] Kolarik | A summary of research investigating echolocation abilities of blind and sighted humans[END_REF]. It must be noted, however, that the amusic individuals in our study did not show increased perceptual sensitivity to beating cues relative to controls, but merely a stronger relative importance of beating over harmonicity in early processing.

Recent evidence suggests that the unpleasantness of dissonant sounds is largely determined by culture, expertise, and context within a musical style, but that even when rated as pleasant, the tension of dissonant sounds can be perceived, allowing them to be discriminated from consonant sounds [START_REF] Lahdelma | Cultural familiarity and musical expertise impact the pleasantness of consonance/dissonance but not its perceived tension[END_REF][START_REF] Popescu | The pleasantness of sensory dissonance is mediated by musical style and expertise[END_REF]. Studies such as the present one, which rely on objective discriminability of consonant and dissonant sounds, do not inform us whether the perception of dissonance is subjectively unpleasant, but merely that it can be discriminated.

Beating and harmonicity cues in consonance and dissonance perception

Behaviorally, participants in our study detected dissonant deviants more easily in a stream of consonant standards than the reverse. This effect is in line with previous evidence for a behavioral advantage for detecting dissonance [START_REF] Schellenberg | Frequency ratios and the discrimination of pure tone sequences[END_REF], an effect which has also been observed in infants [START_REF] Schellenberg | Natural musical intervals: Evidence from infant listeners[END_REF]. More generally, the advantage for detecting dissonance may be an example of perceptual asymmetry due to feature extraction.

In both auditory (e.g. [START_REF] Cusack | Perceptual asymmetries in audition[END_REF][START_REF] Ruggles | Perceptual asymmetry induced by the auditory continuity illusion[END_REF] and visual perception (e.g. [START_REF] Treisman | Feature analysis in early vision: Evidence from search asymmetries[END_REF], observers are better able to detect the presence of an extracted feature than its absence. The behavioral advantage for dissonance detection suggests that dissonance cues (beating and inharmonicity) may be extracted as features by the auditory system, whereas their opposites (lack of beating and harmonicity) are only detectable as the absence of a feature.

More surprising than the behavioral effect is the MMN advantage we observed for consonant deviants over dissonant deviants, which runs in the opposite direction to behavioral results. It also runs opposite a recently reported effect of larger MMNs for dissonant deviants than for consonant deviants [START_REF] Crespo-Bojorque | Early neural responses underlie advantages for consonance over dissonance[END_REF]. However, the stimuli in that study were slightly different from those in the present study: whereas the previous study used pairs of simultaneous tones forming consonant or dissonant harmonic intervals, the present study used single complex tones containing isolated low-level dissonance cues. The discrepancy between the present study and Crespo-Bojorque et al. ( 2018) is perhaps due to the fact that all tones in that study were individually harmonic, although dissonant combinations produced inharmonicity and beating in their interactions. A recent study also found larger MMN amplitudes for harmonic sounds than for inharmonic sounds in amusics and controls [START_REF] Quiroga-Martinez | Enhanced mismatch negativity in harmonic compared with inharmonic sounds[END_REF]. In that study, deviants and standards were either both harmonic or both inharmonic, unlike the present study in which deviants differed from standards in terms of harmonicity. Nevertheless, Quiroga-Martinez et al. ( 2022) provide converging evidence for the asymmetry in processing of harmonic and inharmonic sounds. An earlier study also supports our finding of a clear MMN to harmonic deviants: [START_REF] Jones | Sensitivity of human auditory evoked potentials to the harmonicity of complex tones: Evidence for dissociated cortical processes of spectral and periodicity analysis[END_REF] presented rare, deviant harmonic complexes in a stream of mostly inharmonic complexes, in a condition comparable to HDEV in the present study, and observed an MMN. However, as the opposite condition was not tested in that paper, it provides no specific agreement with the present study's finding for increased MMN to consonant deviants over dissonant deviants. In the present study, the MMN advantage for consonant deviants did not interact with group, suggesting that the asymmetry is present for both amusics and controls. In any case, the direction of the MMN advantage for consonant or dissonant stimuli has no direct bearing on the main findings of the present paper, as an MMN in either case indicates an early brain response indexing detection of the change.

The advantage we observed for behavioral detection of dissonance, confirming previous effects [START_REF] Schellenberg | Frequency ratios and the discrimination of pure tone sequences[END_REF][START_REF] Schellenberg | Natural musical intervals: Evidence from infant listeners[END_REF], seems overall easier to explain than the opposite MMN advantage for consonant deviants, for which previous evidence is mixed [START_REF] Crespo-Bojorque | Early neural responses underlie advantages for consonance over dissonance[END_REF][START_REF] Jones | Sensitivity of human auditory evoked potentials to the harmonicity of complex tones: Evidence for dissociated cortical processes of spectral and periodicity analysis[END_REF][START_REF] Quiroga-Martinez | Enhanced mismatch negativity in harmonic compared with inharmonic sounds[END_REF]. It may be that early processing of consonance is not guided by the same incentives as later conscious processing of consonance, leading to opposite advantages for consonant and dissonant deviants at these two stages of processing. In early stages, the MMN advantage for consonant deviants might be incentivized due to asymmetry in the entropy of harmonic and inharmonic signals, as suggested by [START_REF] Quiroga-Martinez | Enhanced mismatch negativity in harmonic compared with inharmonic sounds[END_REF]. Within a predictive coding framework [START_REF] Kanai | Cerebral hierarchies: Predictive processing, precision and the pulvinar[END_REF][START_REF] Rao | Predictive coding in the visual cortex: A functional interpretation of some extra-classical receptive-field effects[END_REF], increased MMNs for consonant deviants may reflect a higher precision and thus increased weight of the prediction error, due to the lower entropy of a harmonic deviant signal in comparison with the higher entropy of an inharmonic deviant signal. Thus, even if both kinds of deviants violate predictions of equal strength, consonant deviants may receive increased weight as prediction errors due to their decreased entropy. Because consonant sounds tend to have more salient pitch, a larger response to consonant deviants may also be related to the pitch onset response, an observed increase in activity in Heschl's gyrus at the onset of periodic sound, with no equivalent response at pitch offset [START_REF] Gutschalk | Temporal dynamics of pitch in human auditory cortex[END_REF][START_REF] Krumbholz | Neuromagnetic evidence for a pitch processing center in Heschl's gyrus[END_REF]. But if consonant deviants are more salient in early processing, how can we explain the behavioral advantage for dissonant deviants? There are several reasons dissonant deviants may be easier to detect when applied to real-world environments: dissonance may be more likely to indicate a threat, and dissonance may be overall rarer in the auditory world. There may also be an effect of long-term experience, whereby listeners have much more practice identifying dissonance against a consonant backdrop than the reverse.

Limitations in measuring the MMN

The present study focused on stimuli with low levels of dissonance by measuring thresholds in Experiment 1 and presenting stimuli for MMN measurements in Experiment 2 at constant differences near threshold. Although this approach allowed us to detect a behavioral impairment for beating perception in amusic individuals that was not detected by [START_REF] Cousineau | The basis of musical consonance as revealed by congenital amusia[END_REF], it also meant that our analyses of behavioral sensitivity in the MMN experiment were conducted on data near chance performance, and that our EEG analyses were conducted near the threshold for emergence of MMN. The noise inherent in both of these measurements at such low levels may have hampered our statistical ability to detect differences between groups or conditions, as behavioral performance above chance and the presence of an MMN were not confirmed for every group in every condition. This was especially true for the amusic participants, whose behavioral sensitivity for oddball detection in Experiment 2 was only significantly above chance in one condition out of four (BDEV). Future studies might further explore this phenomenon by presenting stimuli with larger levels of dissonance in order to observe a more robust MMN response. It may also be considered a limitation of our study that not all participants completed both experiments, meaning that thresholds were known for some but not all participants in Experiment 2.

Another possible reason for small overall MMN amplitudes in the present study was the variability of the standard stimulus, which changed in F0 for each stimulus presentation. The variability of F0 was necessary in our study to ensure that responses could be interpreted as detection of dissonance, and not as perception of a change in pitch. However, most MMN studies are done using a constant, invariable standard, and the variability in our standard stimulus may have led to decreased MMN amplitude. In addition, stimuli in our study were largely dissonant overall, because three out of four tone types were inharmonic (inharmonic, no-beating, and beating). This was a necessary control measure to ensure that beating stimuli were detected using beats and not using the presence of inharmonic components. However, it may have reduced the salience of the consonance contrast along the beating axis, since both tone types on that axis are dissonant.

Conclusions

Our present findings revealed reduced behavioral sensitivity in amusic participants to two cues that have been implicated in consonance and dissonance perception: beating and inharmonicity. However, our EEG results also suggest that the MMN was not impaired overall in amusic relative to control participants, but inharmonicity and beating may be differently impacted in congenital amusia, with beating cues given relatively more weight than harmonicity cues in participants with amusia. Taken together, our findings are compatible with the view that inharmonicity and beating each contribute to dissonance perception, but that the relative weight of beating cues over inharmonicity cues may be increased for amusic individuals in comparison to control participants.

ACKNOWLEDGMENTS

Figure 1 .

 1 Figure 1. Stimuli manipulating harmonicity and beating cues. Temporal waveforms and frequency spectra of stimuli for harmonicity (left) and beating (right) conditions, with vertical dashed lines showing the 1 st , 2 nd , 3 rd , 5 th , and 9 th components in a harmonic series. Harmonic complexes (A) contained the five components shown, with a decaying spectral envelope. Inharmonic complexes (B) were shifted up relative to harmonic complexes by a uniform distance in linear frequency. No-beating stimuli (C) were inharmonic, with frequency components jittered relative to a harmonic series. Beating stimuli (D) introduced a single sideband component 30 Hz above or below each component in the no-beating stimuli, with a uniform level difference between sidebands and original components. (E) shows the timing of a trial on the 3AFC discrimination task used in Experiment 1. Participants identified the target (red) by comparing against two references (blue), with target position randomized on each trial.

Figure 2 .

 2 Figure 2. Behavioral results for discrimination of harmonicity and beating cues by amusic and control participants. Top: thresholds measured with 3AFC adaptive tracking (Experiment 1) for inharmonic shift (harmonicity, A) and single sideband depth (beating, B), for controls (green, N = 11) and amusics (purple, N = 12). Dashed lines indicate levels chosen for the constant-stimuli oddball paradigm in the EEG study. Error bars show ±1 SEM. Individual thresholds are shown in (C).

Figure 4 .

 4 Figure 4. Behavioral results during the active task of Experiment 2. Behavioral sensitivity (d) for identifying deviants is plotted for the harmonicity contrast (A) with an inharmonic deviant (IDEV) or a harmonic deviant (HDEV), and for the beating contrast (B) with a beating deviant (BDEV) or a no-beating deviant (NDEV), for control (N = 21) and amusic (N = 19) groups. Chance performance corresponds to a d of 0. Individual performance for IDEV and BDEV is shown in (C).

Figure 5 .

 5 Figure 5. ERPs to standard and deviant stimuli at Fz by group and condition. Responses are shown at electrode Fz for each of the four types of stimulus, for controls (top row) and amusics (bottom row). Each plot compares a deviant to its acoustically identical standard (the same sound in a different context from the opposite condition). Blue and red colored regions show ±1 SEM. Gray regions indicate significant MMN across all participants, observed for harmonic and no-beating sounds. Orange regions indicate significant P3a across all participants, observed for harmonic sounds.

Figure 6 .

 6 Figure 6. Topography of MMN and P3a responses to consonant stimuli. The difference amplitude (deviant minus standard) across the scalp is shown, averaged over two time periods: 150-300 ms (MMN, odd columns) and 300-450 ms (P3a, even columns), for harmonic sounds (left) and no-beating sounds (right), for controls (top) and amusics (bottom). Small black dots indicate electrode positions. See Figure S2 for the topographies of nonsignificant responses for dissonant deviants.

  [t(1,38) = -1.26, p = 0.22] and only a marginally significant difference for beating [t(1,38) = 1.78, p = 0.084]. Within-group comparisons (paired t-tests) also showed no significant

Figure 7 .

 7 Figure 7. MMN amplitude and difference waves by group and condition. Difference waves at Fz are plotted for controls (green) and amusics (purple) in each condition (A-D).Purple and green colored regions show ±1 SEM. Shaded gray regions in (A) and (C) show significant MMN at Fz across groups in response to harmonic and no-beating stimuli, while dashed gray rectangles in (B) and (D) show these same clusters for comparison for inharmonic and beating sounds, where no MMN was observed. The shaded orange region in (A) shows a significant P3a for harmonic stimuli, while the dashed orange rectangles in (B-D) show this same cluster for comparison for other sounds where no P3a was observed. (E) shows mean MMN amplitude, averaged within the relevant spatiotemporal cluster for each group and condition. Error bars show ±1 SEM. For harmonic and no-beating stimuli, averages were computed in the cluster for that stimulus across both groups. As no significant clusters were identified for dissonant stimuli, inharmonic and beating stimuli borrowed the clusters for harmonic and no-beating stimuli, respectively. (F) is as (E), but for P3a amplitude, with other sounds borrowing the cluster for harmonic stimuli.

  This work was supported by a grant from the Erasmus Mundus Student Exchange Network in Auditory Cognitive Neuroscience, by LabEx CeLyA ("Centre Lyonnais d'Acoustique", ANR-10-LABX-0060), LabEx Cortex ("Construction, Function and Cognitive Function and Rehabilitation of the Cortex", ANR-11-LABX-0042) of Université de Lyon, within the program "Investissements d'avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR), by the AMBISENSE ("Access to Perceptual Ambiguity") grant from the French National Research Agency (ANR), and by NIH grant R01 DC005216. 6. REFERENCES Alain, C., Arnott, S. R., & Picton, T. W. (2001). Bottom-up and top-down influences on auditory scene analysis: evidence from event-related brain potentials. In Journal of experimental psychology. Human perception and performance (Vol. 27, Issue 5, pp. 1072-1089).

Figure S1 .

 S1 Figure S1. Thresholds for pure-tone AM detection. Thresholds are shown with average and SEM (left), and as individual data compared against single-sideband beating detection thresholds (middle) and against inharmonic shift thresholds (right). Significant correlations were observed between AM and Beating thresholds [r = 0.73, p < 0.001], and between AM and Harmonicity thresholds [r = 0.56, p = 0.005].

Figure S2 .

 S2 Figure S2. Topography of MMN and P3a responses to dissonant stimuli. As figure5, but for dissonant stimuli (inharmonic and beating), where no significant MMNs or P3as were observed (as opposed to consonant stimuli shown in figure5, where significant differences were found).

Figure S3 .

 S3 Figure S3. Temporal evolution of MMN topography. The evolution of the difference amplitude (deviant minus standard) for each of four deviant types is shown (rows 1-4), at each of 10 time points (columns 1-10), averaged across all participants. Red dots show electrodes and time points involved in significant MMN clusters for harmonic sounds (row 1) and nobeating sounds (row 3).

Controls (N=11) Amusics (N=12) p value Age (years)

			Tillmann et al. (2009) for a pure tone at 512
	Hz. All participants provided written informed consent and were compensated for their
	participation. Study procedures were approved by the required ethics committee, the Comité de
	Protection des Personnes (CPP), Sud-Est II.
		37.0 (16.3)	38.7 (14.9)	0.79
	Education (years)	15.7 (2.1)	15.4 (2.8)	0.76
	FDL

(semitones) 0.20 (0.13) 2.08 (1.56) < 0.001 MBEA: global (percent) 89.3 (3.0) 71.3 (6.5) < 0.001 MBEA: pitch (percent) 89.4 (5.2) 68.9 (7.8) < 0.001Table 1 . Comparison of amusic and control samples in Experiment 1 by demographic variables and music perception scores. Mean

 1 values are listed, with standard deviations in parentheses. Bold indicates a p value less than 0.05 in a two-tailed independent t-test between groups. Congenital amusia is identified using the Montreal Battery of Evaluation of Amusia (MBEA), with a global cutoff score of 78% correct over six subtests

  As in Experiment 1, control participants were matched to amusic participants in terms of age, education, gender, and handedness (see Table2). The only participant who reported any musical training was one control participant who reported one year of musical training (not the

		(N=21)	Amusics (N=19) p value
	Age (years)	32.3 (14.4)	30.7 (14.4)	0.73
	Education (years)	15.3 (2.2)	15.0 (2.7)	0.71
	FDL (semitones)	0.29 (0.15)	1.33 (1.48)	0.003
	MBEA: global (percent)	88.2 (3.5)	73.4 (6.0)	< 0.001
	MBEA: pitch (percent)	88.7 (4.8)	70.2 (6.6)	< 0.001

same participant as in Experiment 1). Congenital amusia was identified with the MBEA, and FDLs were measured with the same procedure as in Experiment 1. All participants provided written informed consent and were compensated for their participation. Study procedures were approved by the required ethics committee, the Comité de Protection des Personnes (CPP), Sud-Est II.

Table 2 . Comparison of amusic and control samples in Experiment 2 by demographic variables and music perception scores.

 2 Mean values are listed, with standard deviations in parentheses. Bold indicates a p value less than 0.05 in a two-tailed independent t-test between groups. Details as in Table 1. 33% of amusic participants. Auditory stimuli were presented diotically via MCL Samar CSQ-ECM insert earphones during EEG recording.