text:
# NetNeg: A Connectionist-Agent Integrated System for Representing Musical Knowledge

## 1 Introduction

Researchers in computer music have chosen to use techniques from Artificial Intelligence (AI) to explore complex musical tasks at the cognitive level. These include tasks such as composition, listening, analysis, and performance. Research in AI can also benefit from results in music research; in music, for example, aspects such as time and hierarchical structure are inherent to the domain.

Simulating and modeling a musician’s activities are tasks that are appropriate for experimentation within the framework of artificial intelligence. The cognitive processes a musician undergoes are complex and non-trivial to model. Whenever we are involved in any musical activity, we are faced with symbolic and sub-symbolic processes. While listening, our aesthetic judgment cannot be applied by following explicit rules solely. Applying a learning mechanism to model the task of listening \[BT91, GB96, BG96, BG97\] has been shown to be a convenient (and appropriate) way to overcome the explicit formulation of rules. Nevertheless, some of these aesthetic processes might have a symbolic representation and might be specified by a rule-based system \[Jac91\].

The contribution of this work to AI is in the area of knowledge representation. To demonstrate the advantages and computational power of our hybrid knowledge representation, we design a model that describes the different aspects a user might be interested in considering when involved in a musical activity. The approach we suggest in this work enables the musician to encode his knowledge, intuitions, and aesthetic taste into different modules. The system captures these aspects by computing and applying three distinct functions: rules, fuzzy concepts, and learning.

Creating contrapuntal music in real time is a complex and challenging domain of research. A single paradigm may not be sufficient to deal with this kind of music. We therefore suggest using this music creation task as a domain in which to test the feasibility of our hybrid knowledge representation.

By choosing a specific task, we can examine the performance of the hybrid system. In addition to the theoretical interest in exploring such an architecture, we believe that this composition system can serve as an interactive tool for a composer, or as a real time performance tool.

The specific case study we have chosen to experiment with is the polyphonic vocal style of the Sixteenth Century; more specifically, we investigate two-part species counterpoint (i.e, bicinia).

#### First Species Counterpoint:

this is the first species, the most restrictive one, out of five species defined in species counterpoint music. Following \[Ran96\]:

> The progressive arrangement of the method, in dialogue form, with the rules for each species dependent more or less on the restrictions of the preceding was widely admired for its pedagogical value.

In first species counterpoint, the cantus firmus (i.e., one of the two voices) is given in a whole note representation. The counterpoint (i.e., the second voice) is created by matching a note against another note in the cantus firmus. This matching follows specific rules as we explain in Section 5.2.

The specific task we examine is different in some important respects from the cognitive task of composing counterpoint melodies. First, our system creates both parts of the melody. Second, we do not incorporate any backtracking process, since we deal with composition in real time. Nevertheless, the system architecture exploits the dynamic context to produce the proper continuation of a melody (i.e., the already chosen notes in the past influence the future choices in real time).

NetNeg, is composed of two main sub-systems. One sub-system is implemented by a modified version of Jordan’s sequential neural network \[Jor86\]. This net learns to produce new melody parts. The second sub-system is a two-agent model based on Distributed Artificial Intelligence \[BG88\]. These agents compose the two parts of the melody according to the rules of the style. These agents negotiate with one another to maximize the global utility of the whole system, which for our purposes should be interpreted as the global quality of the composition.

In spite of the simplicity of the problem, our approach can serve as a basis for further investigation of more complex musical problems. This simple domain could have been formulated in a rule based system. Nevertheless, our aim was to choose a starting domain that we could evaluate and in which we could control the complexity of the process. Our hope is that in more complex tasks, our system would be able to integrate the performance of both symbolic and sub-symbolic musical knowledge, as will be shown for the simpler case in the following sections.

In this work, we want to emphasize the promising potential of using the hybrid system approach for building models of musical activities at the cognitive level. Moreover, dealing with the problem of creating music in real time opens up the possibility of building real time interactive applications that combine the activities of a musician and a computer.

The paper is organized as follows. First, we present background information regarding AI methodologies applied to music, and software agents and DAI. The general architecture of the system we have designed is then described, together with the two main modules of the hybrid system. We also show results from experiments performed with each module separately. Finally, we demonstrate the influence of both components in experiments run using the entire system, NetNeg.

## 2 Artificial Intelligence and Music

In this section we describe some representative research that applies Artificial Intelligence (AI) methodologies (i.e., symbolic, logic, connectionist and hybrid approaches) to music. A detailed overview of music systems that use AI tools can be found in \[Cam93\].

### 2.1 The Symbolic Approach

In the symbolic approach, knowledge about the world is represented in an appropriate language. The symbols described in this language can be manipulated by a machine to infer new knowledge.

One piece of research that demonstrates the symbolic approach to music is EMI (Experiments in Music Intelligence) designed by David Cope (see \[Cop91\] and a later work \[Cop96\]). The EMI project focuses on the stylistic replication of individual composers. EMI discovers patterns shared by two or more compositions from a specific style. These patterns are called musical signatures. The patterns are detected during a pattern “almost” matching process (to distinguish from a regular pattern matching process). Patterns are weighted by how often they appear, and musical events (e.g., intervals) are counted and represented as a statistical model. The program fixes the signatures in an empty form in the locations where these signatures were found in the first input work. Then, the program composes music by filling the spaces between the signatures according to music rules and the statistical model. Proper interpolation of this new music relies on an augmented transition network (ATN). The ATN orders and connects appropriately composed materials according to the style, and fleshes out a new work.

### 2.2 The Logic Approach

In the logic approach, knowledge is represented using logical formalisms. New knowledge is inferred by applying logical operations and manipulating this logic-based knowledge.

A representative piece of research that demonstrates the logic approach to music is Choral — an Expert System for Harmonizing Chorales in the Style of J.S. Bach of Kemal Ebcioglu \[Ebc92\]. Choral is an expert system that harmonizes four-part chorales in the style of Bach.

The system contains about 350 rules, written in the form of first-order predicate calculus (in a logic programming language called BSL). The rules represent musical knowledge from multiple viewpoints of the chorale, such as the chord skeleton and the melodic lines of the individual parts. Choral uses an analysis method taken from Schenker \[Sch69, Sch79\] and the Generative Theory of Tonal Music of Lerdahl and Jackendoff \[LJ83\].

The Choral system harmonizes chorale melodies using the generate and test method. The generate section contains condition-action pairs: all possible assignments to the $`n`$th element of the partial solution are sequentially generated via the production rules. The test section contains constraints — if a candidate assignment does not comply with the constraints, it is thrown away. The recommendations section contains heuristics — the successful candidates are weighted by the heuristics and are saved as a sorted list. The program attempts to continue with the best assignment to the element $`n`$. If a dead-end is encountered, a backtracking return is made to this point, with the next best assignment as defined by the sorted list. The heuristics in the search are used for biasing the search toward musical solutions (by changing the order of facts and rules for the search in the data base and for the backtracking).

The program has reached an acceptable level of competence in its harmonization capability. Its competence approaches that of a talented student of music who has studied the Bach chorales. Nevertheless, problems occur with Schenkerian analysis knowledge base, and a general criticism is made by experts as to the lack of excitement and global coherence. The experts also report that they use transformations of solution prototypes to solve a new problem.

### 2.3 The Sub-symbolic Approach

Connectionist researchers believe that an intelligent machine should reflect the Central Nervous System (CNS). Knowledge learned by the machine is expressed by the states and the connections between simple processing units (neurons).

Artificial Neural Networks (ANN) are information processing systems (IPS) that have certain performance characteristics in common with biological neural networks. ANN developed as generalizations of mathematical models of human cognition or neural biology. The ANN paradigm enables learning from a set of examples, avoiding the need to formulate rules. The ANN researcher deals with issues concerning representation, architectures, and learning algorithms. Their main concern is to choose a set of examples that show what is the requested behavior; they do not need to handle any procedural details regarding how to solve the problem algorithmically.

ANN assumptions include the following. Information processing occurs at many simple elements called neurons. Signals are passed between neurons through connection links. Each connection link has an associated weight that typically multiplies the signal transmitted. The weights represent the information being used by the net to solve a problem. Each neuron usually applies a nonlinear activation function to its net input (sum of the weighted input signals) to determine its output signals.

Listening, performing, and some other musical activities can be represented using a sequential stream of information. The choice of Jordan’s sequential net (\[Jor86\]) is appealing in such cases. Jordan’s sequential net is a version of the back-propagation algorithm \[RHW86\]. Using the learning algorithm, the sequential net is able to learn and predict sequential elements (such as the sequence of a melody’s notes or harmonic progression).

The sequential net contains three fully-connected layers. The first layer contains a pool of state units and plan units. The second layer is the hidden layer, and the third layer is the output layer. The output layer and the state units contain the same number of units. The output layer is fed back into the state units of the first layer for the computation of the next sequential element. The value of a state unit at time $`t`$ is the sum of its value at time $`t1`$ multiplied by some decay parameter (the value of the decay parameter is between 0 to 1) and the value of the corresponding output unit at time $`t1`$. The state units represent the context of the current sequential element, and the output layer represents the prediction of the net for the next sequential element.

Peter Todd \[Tod91\] suggested exploiting the Jordan sequential net for predicting sequential musical elements. His neural network model presented a connectionist approach for algorithmic composition. In the learning phase, the net learns a set of melodies’ notes. Each melody is associated with a unique label encoded in the plan units. In the generalization phase, new melodies are produced by interpolation and extrapolation of the labels’ values encoded in the plan units. The resulting melodies share similarities with the melodies within the learning set. These similarities are unique and different from those resulting from other methods, and they are interesting from the compositional aspect.

Two of the authors of this paper together with Naftali Wagner (see \[GLW98\]) suggested the use of a sequential neural network for harmonizing melodies in real time. The net learns relations between important notes of the melody and their harmonies and is able to produce harmonies for new melodies in real time (i.e., without knowledge of the continuation of the melody). The net contains a sub-net for representing meter that produces a periodic index of meter necessary for viable interpretations of functional harmonic implications of melodic pitches. This neural network model suggests a method of building a system for automatic generation of real-time accompaniment in live performance situations. Such a system can be a basis for enhancing musical electronic instruments, educational software or other real time interactive applications (such as NetNeg).

### 2.4 The Hybrid Approach

In the hybrid approach, knowledge about the world is represented by an integration of a sub-symbolic system and a symbolic system (e.g., a neural net can be integrated with a rule-based agent system).

A key motivation for the hybrid approach is the assumption that handling the complexity of AI tasks is beyond the reach of a single paradigm. Melanie Hilario (see \[Hil95\]) distinguishes among various hybrid approaches (in her terminology, neurosymbolic integration). She suggests classifying approaches into two strategies: unified strategies and hybrid strategies.

Unified strategies enrich neural networks with symbolic capabilities. Hybrid strategies combine neural networks and symbolic approaches at different levels. Hybrid neurosymbolic models can be either translational or functional hybrids. Translational hybrid systems use neural networks as the processors. The symbolic approach is applied on the network input and targets. Functional hybrid systems exploit both the neural network and symbolic components equally.

The system we present in this work is functional hybrid. Moreover, it is loosely coupled, since each of the components (i.e., the symbolic and sub-symbolic) act locally in time and space, and the interaction between them is always initiated by one of them. In our case, the integration of both components is appropriate to the chainprocessing integration mode as explained in \[Hil95\]. Specifically, we can look at one of the processes as doing the main task, and the other as pre/post processing the relevant information. In NetNeg, either of the two modules can be viewed as the main module, and in charge of the other.

To the best of the authors’ knowledge, the integration of a symbolic system with a sub-symbolic system, and in particular the integration of a rule-based agent module with a neural network module for representing musical knowledge, is novel.

Another known hybrid system is HARP \[CCIM95\] (Hybrid Action Representation and Planning). This system has been designed for computer-assisted composition, performance, and analysis. As explained in \[CCIM95\], HARP is considered hybrid since it combines different formalisms. The symbolic module consists of a semantic net together with a temporal logic with production rules. The sub-symbolic module is composed of a system of cooperative agents. It is not clear whether the sub-symbolic component in this system handles only the representation of knowledge, or whether it also handles the processing and integration of data. However, NetNeg processes data at a sub-symbolic level (i.e., the neural network), and also processes data at the symbolic level (i.e., the rules about which the agents can reason). In addition, NetNeg integrates the results of this processing, namely each component makes use of the results of the other’s as structures for its own input.

## 3 Software Agents

Agents (robots or software agents \[WM95, WMT96\]) are functional, independent software modules that are programmed to act on behalf of the user. Among the salient features of software agents are autonomy, adaptation, and sociability. Agents are autonomous in the sense that after they are given a goal, they can decide how it would be achieved in terms of the steps to be taken and the time needed for its execution. Agents might act in static as well as in dynamic environments. An agent might be embedded in a world in which it is the only software entity, or the agent might need to interact with other agents of the same or different types (homogeneous or heterogeneous societies). In these cases, agents can benefit if they are adaptive; i.e., agents that learn from their environment and/or the other agents with which they interact or whose actions interfere.

There has been research on the standardization of communication languages (e.g., KQML) for agents, allowing agents of differing types to communicate with one another. Agents might also build beliefs models of the other agents in the environment and behave accordingly. Agents have been built that cooperate with one another, even in cases where communication among them does not exist. This has been achieved by imposing social laws on their behavior. Agents might also be capable of communicating with their human users.

Distributed Artificial Intelligence (DAI) is the area in AI that investigates the behavior of societies of agents. Research has been divided into two main streams: Cooperative Problem Solving (CPS) and Multiagent Systems (MAS).111More recently, “multiagent systems” has been used as another name for the entire field of DAI. The main difference between these approaches lies in the global objective of the system of agents. In CPS systems, agents are assumed to be cooperative and to have a common goal. The agents have been designed together, and will assist the others for the group’s benefit. In MAS, agents might have been designed by different designers. Agents might be self-interested, and they have their own personal goals. In these systems, agents might benefit from cooperating with one another, but their actions or goals might also conflict.

In heterogeneous environments, even when the agents might be self-interested and their goals might differ, agents may be able to coordinate their actions, and also may benefit if they cooperate.

One of the main research areas DAI is concerned with regards applying coordination protocols to multiagent systems. The agents programmed to follow these protocols, or agents that are able to learn how to behave, coordinate with other agents in the same system in order to achieve global goals, or to avoid conflicts. To study different coordination approaches, different models have been studied, including negotiation \[Smi78, Dur88, KW91, ZR93, RZ94\], economics \[MFH88, Wel92, Kra93\], social laws \[GR94, TM89, ST92\], and others \[DL92, ER91, GK93\].

One way used by agent designers to quantify the agents’ performance is to let the agents compute a utility function. In certain systems, this function represents the gain of the agent from choosing an action because of the existence of other agents, in contrast to the cost incurred by working alone in the world. Other notions of utility might describe how much information an agent has, or how well the agent does for a given choice of action. Whenever agents are self-interested, they can express their interests and preferences in their utility function.

In order to achieve the goals assigned to the agents, these agents choose actions to perform. The algorithms that describe the agents’ behavior take into consideration the utility values, and according to them, the agents choose their actions. Therefore, the actions that the agents will perform are strictly related to the computation of the utility function, which specifies the agents’ interests.

The computation of this utility function and its semantics together with the autonomy, adaptability, and sociability characteristics of the agents, make a multiagent system richer in expressiveness and in the possible interactions that might emerge than a static rule-based system. Agents might change their behaviors to be able to respond better to other agents operating in the same world. The utility function might take into consideration facts or terms that would be difficult to define explicitly by a data base of rules. Therefore, in this research we implement a utility function approach for our agents. Later in this article we also show how the function can be formulated in a different way, so as to express differing interests of agents (e.g., one agent can be designed to prefer a better melody line by increasing the weight given to the network recommendation, and another agent might decrease the weight given to the contrary motion term).

Research in Distributed Artificial Intelligence (DAI) \[BG88\] can also contribute to developing new methods for computer music. For example, an interesting research question to investigate is the analogy between the dynamics of the performance of a group of musical instruments or voices in a vocal ensemble to multiagent systems and their interactions in the DAI sense.

## 4 The Nature of the General Architecture

We distinguish among three aspects that are important for a musician. The overall design of our system has been guided by these aspects: his knowledge, intuitions, and aesthetics. The musician’s knowledge (e.g., rules for a known style, or rules he has invented), intuitions (i.e., fuzzy concepts about the music he is interested in composing), and aesthetic taste (e.g., by learning regularities that appear in the training examples), can be encoded in different modules.

The system is composed of agents; we can look at musical activities that can be decomposed into functional components. All these components interact in order to achieve a global goal. Many musical examples involve such interacting processes: producing the voice leading of a vocal piece, a string quartet performance, or composing different parts of a polyphonic melody. Each such functional component can be implemented and conceptualized as an autonomous agent. Then, the global goal or activity can be understood as the goal of the multiagent system and the interactions among the parts are the social interactions among the agents (e.g., by coordinating, communicating, teaching). In our case, the agents communicate, cooperate and share tasks in order to improve the global performance of the system. Each agent knows rules of a specific style, and heuristic rules that take into consideration different aspects of the problem that the system is trying to solve. The aesthetic taste referred to above might be captured by a learning mechanism (e.g., a neural network) that will give advice to the agents.

An example that we have implemented and will present in the following sections, refers to the problem of composing polyphonic music in real time. This implementation demonstrates a specific solution using the approach presented in this section.

## 5 NetNeg’s Architecture

In many musical styles, the composer needs to create different sequences of notes (i.e., melody lines) that will be played simultaneously. Each sequence should follow some aesthetic criterion, and in addition the sequences should sound appropriate when combined. This overall composition is the result of many interactions among its components. The musician achieves his overall result by compromising between the perfection of a single component and the combination of sequences as a whole. Thus, in this activity there is a constant tradeoff between the quality of a single sequence versus the quality of the combined group of sequences. When a musician is faced with such a task, he is involved in a cognitive process, that we suggest might be seen as a negotiation process. He has to compromise between the melodies’ notes by choosing from among the permitted notes those that are preferable.

The case study we chose for our experiment deals with first species of two part counterpoint melodies. In NetNeg, we create both parts dynamically, in real time. Therefore, the system is not allowed to perform backtracking. A general view of the architecture of NetNeg is shown in Figure 1.

NetNeg is composed of two sub-systems: a connectionist sub-system and a DAI-based subsystem. The role of the connectionist subsystem is to learn and generate individual parts of the polyphonic melody. In our implementation, the network learned to reproduce a series of learning examples that were taken from \[Jep92\]. Based on this learning process and the set of learning examples, the neural net is able to produce in the generalization phase new individual melody parts. In this phase, the network predicts in the output layer a vector of expectations for the next note in each part of the melody.

Each agent represents one of the voices of the polyphonic music. It is responsible for choosing the tone that will be inserted in its voice at each unit of time. Each agent receives a different output vector from the network. On the one hand, each agent has to act according to its voice’s aesthetic criteria; and on the other hand, it has to regard the other voice-agent such that both together will result in a two-part counterpoint. Both agents have to negotiate over all the other possible combinations to obtain a globally superior result. Thus, they influence the context with their agreement. Given this new context and the initial values of the plan units, the network will predict another output vector. This process continues sequentially until the melodies are completed.

We describe each of these modules separately and then present results from experiments performed with NetNeg.

### 5.1 The Connectionist Subsystem

Each part of the melody is produced independently by a neural network implemented in Planet \[Miy91\]. Todd \[Tod91\] previously suggested a sequential neural network that can learn and generate a sequence of melody notes. Currently, our neural network is based on the same idea, although we have extended it to include the representation of the contour of the melody.

We built a three-layer sequential net, that learns series of notes. Each series is a one part melody. Each sequence of notes is labeled by a vector of plan units. The net is a version of a feedforward backpropagation net with feedback loops from the output layer to the state units (in the input layer). The state units in the input layer and the units in the output layer represent the pitch and the contour. The state units represent the context of the melody, which is composed of the notes produced so far. The output unit activation vector represents the distribution of the predictions for the next note in the melody for the given current context.

The role of the plan units is to label different sequences of notes. In the generalization phase, we can interpolate and extrapolate the values of the plan units so as to yield new melodies. At each step, the net is fed with the output values of the previous step in the state units together with the values of the plan units. These values will cause the next element in the sequence to appear in the output layer and it will be propagated as feedback into the state units (these connections do not appear in Figure 1). The current values of the state units are composed of the previous values multiplied by a decay parameter and the current output values.

The state units and the output layer can represent the notes in different ways. Each note is represented by a binary vector. The pitch is associated with the index of the single 1 in the vector (e.g., RE will be encoded as (10000000) and MI as (01000000) in the Dorian modus222The training set as shown in Figure 2 is written in Dorian modus. The Dorian modus is a scale of pitches where the RE is the highest pitch in the pitch hierarchy. This modus is similar to the pure minor scale and differs in having a higher sixth pitch.). In this implementation, we choose to represent the notes as a vector of 19 units. The first eight units encode the pitch. The next nine units represent intervals between the notes. The last two units describe whether the movement of the melody is ascendent or descendent (we will refer to these units as the movement units).

For example, if the current tone is DO(C), the net predicts both RE(D) and FA(F) as the next best tones, and the ascendent movement unit is on, then the interval can help us to decide which tone to choose (i.e., one tone or two and a half tones). If after the net has chosen the tone SOL(G), it predicts LA(A) or FA(F) and the interval is of one tone, then we could choose whether to descend or ascend based on the activations of the movement units. In order to exploit the information encoded in the output units’ activations, the pitch activations were combined with the interval and the movement activations. The activations of the output units were mapped into a vector of thirteen activations corresponding to the notes in more than an octave and a half.

Each agent receives the 13-length vector, and feeds the state units their agreement (see Figure 1 and Section 5.2). Then, the network predicts another output vector given this new context and the initial values of the plan units. This process continues sequentially until the melodies are completed.

### 5.2 The DAI-Based Subsystem

The agent module was implemented by using the Mice testbed \[MLM+92\]. In the implementation presented in this work, each voice of the bicinia is represented by an agent. Since we are dealing with two counterpoint melodies, then in DAI terms we design a multiagent system composed of two agents. The global goal of the system is to compose the two part melody following the rules of the style. In addition, each single agent has its own individual goal, i.e., to compose its melody by choosing the right notes. In particular, each agent has to act according to the aesthetic criteria that exist for its voice; at the same time, it has to compose the voice in a manner compatible with the other voice-agent such that both together will result in a two-part counterpoint.

At every time unit in our simulations, each agent receives from the network a vector of activations for all the notes among which it can choose. Were the agent alone in the system, it would have chosen the note that got the highest activation from the neural network, meaning that this note is the one most expected to be next in the melody. Both agents’ choices might conflict with respect to the rules of the style and their own preferences. Therefore, we apply a negotiation protocol \[RZ94\] to allow the agents to coordinate and achieve their mutual goals. The agents will negotiate over all the other possible combinations to obtain a globally superior result.

In principle, each agent can suggest any of the $`n`$ possible notes received from the network. Not all of these pairs of note combinations are legal according to the rules of the species. In addition, there are specific combinations that are preferred over others in the current context. This idea is expressed in this module by computing a utility function for each pair of notes. In this sense, the goal of the agents is to agree on the pair of notes that is legal and also achieves the maximal utility value among all options.

At each time unit, for each pair of notes, the agents start a negotiation process at the end of which a new note is added to each of the current melodies. Each agent sends to the other all of its notes, one at a time, and saves the pair consisting of its note and the other agent’s note that a) is legal according to the first species style rules and b) has yielded the maximal utility so far. At the end of this process, the pair that has achieved maximal utility is chosen. Both agents feed their networks with this result as the current context so that the networks can predict the next output. Each agent, then, receives a new input based on this output, and the negotiation step is repeated until the melody is completed.

The term in the utility function that encodes the rules of a given style expresses (in our implementation) the rules of the polyphonic vocal style of the sixteenth century as they appeared in \[Jep92\]. A pair of notes is considered legal according to the following rules:

1. The intervals between pairs of notes in the two part melodies should not be dissonant (i.e., the second, fourth, and seventh intervals are not allowed).
2. There should be perfect consonance (i.e., unison, octave, and perfect fifth intervals) in the first and last places of the melody.
3. Unison is only permitted in the first or last places of the melody.
4. Hidden and parallel fifths and octaves are not permitted.333Following \[Ran96\], “parallel motion of perfect intervals is forbidden, nor may any perfect interval be approached by similar motion”.
5. The difference between the previous and the current interval (when it is a fifth or an octave) should be two (this is our modification).
6. The interval between both tones cannot be greater than a tenth.
7. At most four thirds or sixths are allowed.
8. If both parts skip in the same direction, neither of them will skip more than a fourth.
9. In each part, the new tone is different from the previous one.
10. No more than two perfect consonants in the two part counterpoint, not including the first and last notes, are allowed (this is our modification).

One example of an aesthetic preference or intuition in our current implementation is captured by preferring contrary motion. The function values will be determined according to whether the pairs of notes are legal or illegal based on the rules given above, and whether they are more preferred or less preferred, based on the net advice and fuzzy concepts given by the musician (e.g., contrary motion). The utility function we chose is one example of a function that computes all the aspects we described in Section 4.

More formally, we define the utility function as follows:

$`SysUtility(T_1^t,T_2^t)=[(act(T_1^t)act(T_2^t))+cm(T_1^t,T_2^t)]match(T_1^t,T_2^t)`$

where: $`T_i^t,i\{1,2\}`$ is the tone proposed by agent $`i`$ at time $`t`$. $`act(T_i^t)`$ is the activation of tone $`i`$ as rated by the neural network. The term $`cm`$ characterizes the motion between the previous two tones and the current pair of tones. We will denote the following condition $`cmCond`$ as true when there is contrary motion. Notice that the $`cm`$ values are larger whenever the movement steps are smaller. $`cmCond(T_1^t,T_2^t)\stackrel{\mathrm{def}}{=}\neg (((T_1^t<T_1^{t1})(T_2^t<T_2^{t1}))((T_1^t>T_1^{t1})(T_2^t>T_2^{t1})))`$

Then we define $`cm(T_1^t,T_2^t)=\{\begin{array}{ccc}\frac{1}{|interval(T_1^{t1},T_2^{t1})interval(T_1^t,T_2^t)|}\hfill & \text{ if }cmCond(T_1^t,T_2^t)\text{ }\hfill & \\ 0\hfill & \text{otherwise}\hfill & \end{array}`$

$`match(T_1^t,T_2^t)=\{\begin{array}{cc}1\hfill & \text{if }(T_1^t,T_2^t)\text{ is legal w.r.t. the above rules}\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}`$

We have considered contrary motion in this function because this type of motion produces the most natural and appropriate effect for this kind of music (as noticed by Jeppesen \[Jep92\]). An interesting point to notice is that taking into account the contrary motion term in the function enables the system to produce contrary motion although the network might have suggested movement in the same direction (based on the cantus firmi with which the network was trained).

In this implementation, both agents’ neural networks were trained with the same set of training examples, and both compute the same utility function. In a more general case, we might have a more complex, and richer, multiagent system by implementing agents with different utility functions (i.e., the agents combine or weight in different ways the same terms, or consider other terms to compute the aspects discussed in Section 4). In this way, agents might stick to a specific kind of behavior; agents with different character might be implemented (e.g., an agent that wants its voice to be more salient along the melody).

One way to enrich the kinds of melodies produced is to enable nondeterministic rules. This can be expressed by having a system where one agent can compute the utility of the same pair of notes for the system in different ways. One example is to have a system composed of one agent that prefers more contrary motion than the other. In our case this will be expressed by giving more weight to the $`cm`$ term in the computation of the utility function. This weight might be chosen from a certain distribution. Another example is to have agents that prefer X% of the time skips, and the other prefers Y% steps.

More generally, we can think of each agent as having two different functions. In other words, each agent sees the utility function as a computation of different terms that should be considered. This is an example of a multiagent system in which each agent could be designed by a different designer, and has its own interests and desires. The benefit of the whole system is not necessarily the benefit of each of the agents.

## 6 Experiments

We first ran each subsystem separately to examine the ability of each one of the two approaches (i.e, Neural Nets and agents) to cope with the general problem. We then ran the integrated system; we present results from all of these simulations. In this way, we show the ability of the whole system to produce results superior to the performance of either of the subsystems. Combining the modules gave us a more natural way of dealing with the processing of and representation of our task.

### 6.1 Running the Net Module

The task of the net was to learn to produce new two-part melodies. This case is different from the one faced by the whole system, in which only one-part melodies were taught. Therefore, we needed to represent both parts of the melody simultaneously. We used the same sequential net that was described in Subsection 5.1. In this case, we doubled the number of the units in each layer to represent two notes simultaneously, one for each part. In the learning phase the net was given four melodies, containing the two parts. One example from this set of melodies follows:
V1:$`re8do8mi8lado8silado8re8`$
V2:$`re8la8sol8fa8mi8re8fa8mi8re8`$

Since our notes are taken from one and a half octaves, we represent the notes by their names (i.e., re), and those in the higher octave have an 8 concatenated to their names (i.e., re8). In this phase, the net learned the examples in the set with high accuracy after short training.444For 20 hidden units it took less than 100 epochs to achieve an average error around $`0.0001`$. Each melody had a different label encoded as a unique value in the plan units. After training, we tested the net by supplying as input the four labels 1000, 0100, 0010, 0001, one for each of the four melodies in the set, and the net was able to completely reproduce the sequence without mistakes.

In the generalization phase we chose to interpolate the values of the plan units to produce new melodies. Todd \[Tod91\] demonstrated that the resulting sequences have non-linear similarities to the sequences in the learning set depending on the activations of the plan units. An example of a typical result follows:
The plan vector: (0.3 0.7 0.3 0.7).
V1:$`re8solsido8^{}mire^{}do8re8`$
V2:$`re8fa8^{}sol8la8sol8fa8mi8re8`$

This resulting sequence reflects typical problems we encountered when dealing with this simple approach. The examples in the learning set imposed two different constraints on the net. The constraints regard the melodic intervals between the pitches in each part, and the combinations of pitches in both parts. The net is not able to cope with both constraints consistently, and thus it satisfies each, one at a time. For example in $``$, the combination chosen is not allowed in the specific style, although the melodic interval is fine. In $``$ the descending skip is not permitted, as well as the ascending skip in $``$, but both combinations are fine.

### 6.2 Running the Agent Module

The agents in our system know the rules of the specific style of the melodies we want to compose. They also know how to compute the system utility for a given pair of notes. We have run experiments with the agent module alone. We remove the influence of the recommendations produced by the neural network by giving the agents a vector of zero activations for all the possible notes. In this way, we wanted to check that the voices we will get by solely applying knowledge about interactions between the two parts will lack the features learned by the net in its training phase (i.e., the aesthetics of one part).

We run the module with the utility function described in Section 5.2, where the net’s advice was assigned zero. Since we choose the pair of notes that get the maximal utility value at each step, the result is:
V1:$`re8do8lasollamilare8`$
V2:$`re8mi8fa8sol8fa8sol8fa8re8`$

The melody lacks the features requested from each part. In both voices there are redundant notes (i.e, the appearance of note la in V1, and the series of notes in V2 from the third place to the seventh). There is no unique climax in any of the voices. There are two continuous skips in the last three notes in V1. There are too many steps in V2 (i.e., there is no balance between the skips and the steps).

We also observed that melodies can come to a dead end, when there is no pair of notes that can satisfy the rules of the specific style. In such cases, we have tested additional results that can be produced by the system when the agents are allowed to choose pairs with utility values smaller than the maximum.

### 6.3 Running NetNeg

In this section we present the main simulation performed on the whole system. In the training phase, the network learned to reproduce four melodies that were taken from \[Jep92\]. See Figure 2.

We have tested the performance of the network with different learning parameters, such as the number of hidden units and the values of the plan units. The results we present were produced by a net with 15 units in the hidden layer.

In the generalization phase, given a specific vector of plan units, the network produces a new cantus firmi. We have chosen two different plan vectors for the net that will output the notes for each agent. We run the net, each time with the corresponding plan vectors, and mapped their outputs to two different thirteen activation values. Then, we run the DAI-based module with these inputs. The agents negotiate over the different pairs of possible combinations, computing for each the system utility. Finally, the agents agree upon a legal pair of notes that has yielded the maximal utility; alternatively, the agents might decide that no combination is legal, given the previous note in the melody.

In our current case, the nets are fed with the agents’ agreement and the system continues to run. This process is executed until the two-part melodies are completed. Currently, the length of the melodies is fixed.

A melody that resulted from an experiment we performed is shown in Figure 3. The net was presented with two different plan vectors ((0.8 0 0.8 0) and (0 1 0 1)). The agents computed the utility of the system taking into account the rules described in Section 5.2 and the contrary motion term.

In Figure 3 we can observe that the system gives aesthetic results, quite appropriate for the species style with which we have experimented. Both parts are consistent with the combination constraint, as opposed to the simulation we ran solely with the neural network, where this constraint was not satisfied. Comparing with the simulation run with the agents alone, no redundancy was found in this example. Nevertheless, there is a contour problem as pointed out in (1) and (2) in A1’s melody in Figure 3. According to Jeppesen \[Jep92\], it is preferred to descend by a step and then perform a descending skip. After a descending skip, we are expected to have a compensating ascending movement. In (3), we prefer to approach the last note by a step. A2’s melody is perfect with regard to the contour. There is a single climax as shown in (4).

By running both modules together, we see the combined effect of all the aspects taken into consideration in the utility function. The melody of agent $`A_2`$ is perfect. This reflects the melodies learned by the neural net. The contrary motion term expressed in our heuristic is revealed in the relation between both melodies. The neural network was not trained with melodies such as the one created by agent $`A_1`$. The rules are expressed, for example, in the consonance of the parts of the melody.

The whole system was run only for a deterministic case. The nondeterministic case was run only to show that NetNeg is also capable of having agents computing different functions. In the nondeterministic case, the agents weighted the contrary motion term according to a coin toss between $`0.5`$ and $`1.49`$. We did three simulations, and got the following melodies:

1. V1:$`re8mi8sol8la8sol8mi8fa8re8`$
V2:$`re8do8silasido8lare8`$
2. V1:$`re8do8lasollado8sire8`$
V2:$`re8mi8fa8sol8fa8mi8sol8re8`$
3. V1:$`re8mi8sol8la8sol8fa8sol8re8`$
V2:$`re8do8silasire8sire8`$

In all the examples produced, there are too many steps in the second voice. There is no unique climax in the second voice as well. In general, the first voices are slightly more interesting. In the first example, the second voice is not very interesting; it has too many steps. There is not any balance among the steps and the skips. The only skip is at the last note, exactly where we prefer it less. In the second example there is not any climax in any of the voices. In the third example there is a redundant series in the second voice, (si re8 si re8). The analysis of the interactions among specific types of agents remains for future research.

## 7 Summary and Future Work

The main contribution of this research is in presenting a powerful computational approach for representing musical knowledge.

We have presented a novel computational approach for encoding the knowledge, intuitions, and aesthetic taste of a musician in different modules. In this work, we presented an example of an implementation that enables a human to flexibly guide the system to compose music in a style he chooses, under real-time constraints. The user might express multiple views and levels of knowledge to this system. For example, if he knows examples of the music he wants the system to compose, he can train the neural network with these examples. If he wants the music to follow specific rules he might formulate them in the agent module. In addition, he can regard other factors in the computation of the utility function.

The system is composed of a connectionist module and an agent-based module. The agents decide upon the notes in both melodies. The neural network predicts the expectation for every note to be the next one in the melody. This vector of expectations is passed as input to each of the agents. Each agent knows the rules of the style, heuristics, and the net’s advice. Based on these, the agents then negotiate over the possible combinations of notes until they reach an agreement on notes that, added to the melody, will most greatly “benefit” the system. The pair of notes that has been agreed upon is sent back to the neural networks to build their new context. As a case study, we built a system for composing two-part counterpoint melodies.

We have implemented a specific utility function, but nevertheless our architecture is general enough to run different kinds of functions for achieving other tasks. In a multiagent system, agents may be self-interested. This can be expressed by giving each agent a different utility function or nondeterministic functions. We refer to a function as nondeterministic when, for the same pair of notes, it will return different values. In our work, we started to investigate functions in which the contrary motion term was weighted by a coin toss.

Issues to be further investigated include other ways to integrate both modules, the study of other species (second, third, and fourth species), and polyphonic music in more flexible and more abstract styles. We are also interested in examining how other representations and coordination protocols \[GR96, GR97, GR98\] can influence the performance of the system.

## Acknowledgments

We would like to thank Gil Broza for implementing a C++ version of NetNeg.


format: text

text:
# Untitled Document

On the denseness of the invertible group in Banach algebras

T. W. Dawson and J. F. Feinstein

ABSTRACT

We examine the condition that a complex Banach algebra $`A`$ have dense invertible group. We show that, for commutative algebras, this property is preserved by integral extensions. We also investigate the connections with an old problem in the theory of uniform algebras. \[MSC: 46J10, 46H05\]

Introduction

In this paper we investigate the condition that a complex Banach algebra, $`A`$, have a dense invertible group, $`G(A)`$. Throughout we shall consider only unital, complex algebras; usually they will also be commutative.

The condition was first explored by Robertson in $`[\mathrm{𝟐𝟐}]`$ for $`C^{}`$-algebras. As remarked there, a complete characterisation of it in terms of the topology of the maximal ideal space has been known for some time in the commutative case. It is so fundamental that we state it now: if $`X`$ is a compact Hausdorff space then $`C(X)`$ has dense invertible group if and only if $`\mathrm{dim}X`$, the covering dimension of $`X`$, is not more than $`1`$. For a proof of this fact see for example $`[\mathrm{𝟐𝟎}]`$, Proposition 3.3.2. This book is a useful source of information on dimension.

The condition has since attracted considerable (implicit) attention as the first case of the condition ‘$`\mathrm{tsr}Am`$’ where $`m`$ is a natural number, $`A`$ a topological algebra, and $`\mathrm{tsr}A`$ its ‘topological stable rank’. This notion was introduced in the seminal paper $`[\mathrm{𝟐𝟏}]`$ and for a very useful survey and collection of results on this subject we refer the reader to $`[\mathrm{𝟓}]`$.

We also mention that the condition has been used to characterise commutative $`C^{}`$-algebras in which all elements have square roots ($`[\mathrm{𝟏𝟑}]`$). Furthermore, in Chapter 10 of $`[\mathrm{𝟐𝟎}]`$, the dimension of a compact Hausdorff space, $`X`$, is described precisely in terms of the set of (uniformly closed) subalgebras of $`C(X,\mathrm{})`$ which are integrally closed in $`C(X,\mathrm{})`$. (Recall that an element $`b`$ of an algebra, $`B`$, is said to be integral over a unital subalgebra, $`A`$, if there exists a monic polynomial with coefficients in $`A`$ which has $`b`$ as a root.) However we shall only consider complex Banach algebras here.

In general it is not easy to determine the closure of the group of invertible elements of a Banach algebra. Again we quote an example from $`[\mathrm{𝟐𝟐}]`$: when $`A`$ is the disc algebra, $`\overline{G(A)}`$ is equal to the set of elements of $`A`$ whose zero set lies in the unit circle. Further introductory examples are given in Section 1 of this paper.

Our study of the denseness of the invertible group was prompted by an observation (Theorem 1.7) which sheds light on the old open problem of whether or not there is a non-trivial uniform algebra on the unit interval whose maximal ideal space is equal to the unit interval. However our main result, proved in the section after, is that the property of having a dense invertible group is inherited by integral extensions of a commutative Banach algebra.

1. Notation, Preliminary Examples and Results

We begin by setting out some notation and standard terminology.

The Gelfand transform of a normed algebra, $`A`$, will be denoted $`\widehat{A}`$. The algebra $`A`$ is said to be symmetric if $`\overline{f}\widehat{A}`$ whenever $`f\widehat{A}`$. We shall use the notation $`B_A(a,r)`$ for the open ball of centre $`a`$ and radius $`r`$ in the normed space $`A`$. The unit circle is denoted $`S^1`$; we regard it as a subset of the complex plane.

The following definition, which seems quite standard in the literature, is useful.

DEFINITION 1.1. A subalgebra, $`B`$, of an algebra, $`A`$, is called full if we have $`G(B)=BG(A)`$.

For example, $`R_0(X)`$, the algebra of rational functions on a compact plane set, $`X`$, with poles off $`X`$ and $`C^n(I)`$ are both full subalgebras of their completions with respect to the uniform norm.

EXAMPLE 1.2. Let $`B`$ be the restriction to $`S^1`$ of the algebra of complex rational functions with poles off $`S^1\left\{2\right\}`$. Then $`B`$ is easily seen to be uniformly dense in $`A=C(S^1)`$ (by the Stone-Weierstrass theorem for example). However, $`B`$ is not a full subalgebra of $`A`$ because, for example, the function given by $`z2B`$ is invertible in $`A`$.

For future reference we note the following elementary result.

PROPOSITION 1.3. Let $`A`$ be a Banach algebra with maximal ideal space $`\mathrm{\Omega }`$ such that $`\widehat{A}`$ is dense in $`C(\mathrm{\Omega })`$ (for example if $`A`$ is symmetric). Give $`\widehat{A}`$ the uniform norm. Then $`\widehat{A}`$ has dense invertible group if and only if $`C(\mathrm{\Omega })`$ has.

Proof. It is elementary that $`\widehat{A}`$ is a full subalgebra of $`C(\mathrm{\Omega })`$. Moreover, if $`\widehat{A}`$ is dense in $`C(\mathrm{\Omega })`$ then, since $`G(C(\mathrm{\Omega }))`$ is open in $`C(\mathrm{\Omega })`$, we have from elementary topology that

$$\overline{G(\widehat{A})}=\overline{\widehat{A}G(C(\mathrm{\Omega }))}=\overline{G(C(\mathrm{\Omega }))}$$

where the closures are taken in $`C(\mathrm{\Omega })`$. This shows that if $`G(C(\mathrm{\Omega }))`$ is dense in $`C(\mathrm{\Omega })`$ then the invertible elements of $`\widehat{A}`$ are dense in $`\widehat{A}`$. The converse is trivial.

It follows from facts mentioned in Section 1.2 of $`[\mathrm{𝟓}]`$ that if $`A`$ is a commutative Banach algebra with maximal ideal space $`\mathrm{\Omega }`$ and $`A`$ is regular (that is, the hull-kernel topology on $`\mathrm{\Omega }`$ is the Gelfand topology) then the denseness of $`G(A)`$ in $`A`$ implies that $`C(\mathrm{\Omega })`$ also has dense invertible group. We do not know if the converse is true for regular Banach algebras. Neither do we know any examples of non-regular Banach algebras for which $`G(A)`$ is dense in $`A`$ but $`C(\mathrm{\Omega })`$ does not have dense invertible group.

EXAMPLE 1.4. In $`[\mathrm{𝟐𝟏}]`$ it is shown that if $`A`$ is a unital $`C^{}`$-algebra then $`A`$ has dense invertible group if and only if $`M_n(A)`$ has for every $`n\mathrm{}`$. We remark that the proof given in $`[\mathrm{𝟐𝟏}]`$ applies to all Banach algebras.

In view of the fact that $`M_n(A)=M_n(\mathrm{})\widehat{}A`$ (see for example $`[\mathrm{𝟏𝟗}]`$, p. 43), where $`\widehat{}`$ is the projective tensor product, one might be tempted to conjecture that if $`A_1`$ and $`A_2`$ were commutative unital Banach algebras with dense invertible groups then $`A_1\widehat{}A_2`$ would have dense invertible group. However if we let $`A_1=A_2=C(I)`$ then by a standard result (see for example $`[\mathrm{𝟔}]`$, Proposition 2.3.7) their tensor product, $`B`$, has a maximal ideal space homeomorphic to $`I\times I`$ (dimension 2) and $`B`$ is easily seen to be symmetric. Therefore $`B`$ could not have dense invertible group by Proposition 1.3 above.

PROPOSITION 1.5. Suppose that $`A`$ is a commutative unital Banach algebra which is rationally generated by a single element, $`a`$. (See $`[\mathrm{𝟔}]`$, Definition 2.2.7: we mean that the algebra of elements obtained by applying the rational functions with poles off $`\sigma \left(a\right)`$ to $`a`$ is dense in $`A`$.) If $`\sigma \left(a\right)`$ has empty interior then $`A`$ has dense invertible group.

Proof. This follows from the fact that if $`K`$ is a subset of $`\mathrm{}`$ with empty interior and $`\varphi `$ is a function holomorphic on a neighbourhood of $`K`$ then $`\varphi (K)`$ also has no interior. Thus $`A`$ has a dense set of elements whose spectra have no interior, which, as is noted in $`[\mathrm{𝟕}]`$, is equivalent to the condition $`\overline{G(A)}=A`$.

For the definition of a weight sequence and Beurling algebras, which appear in the next example, we refer the reader to $`[\mathrm{𝟔}]`$, Definition 4.6.6.

COROLLARY 1.6. Ler $`\omega `$ be a weight sequence on $`\mathrm{}`$ and let $`A`$ be the associated Beurling algebra, $`\mathrm{}^1(\mathrm{},\omega )`$. Then $`A`$ has dense invertible group if and only if $`\rho _{}:=lim_{n+\mathrm{}}\omega _n^{1/n}=lim_{n+\mathrm{}}\omega _n^{1/n}=:\rho _+`$.

Proof. It is standard (see for example $`[\mathrm{𝟔}]`$, Theorem 4.6.7) that $`A`$ is unitally polynomially generated by $`\{\delta _1,\delta _1{}_{}{}^{1}\}`$ and so rationally generated by $`\left\{\delta _1\right\}`$ where $`\delta _1`$ is the characteristic function of $`\left\{1\right\}`$. It is also standard that the maximal ideal space of $`A`$ can be identified with the annulus $`\{w\mathrm{}:\rho _{}\left|w\right|\rho _+\}`$. By standard results in dimension theory $`\mathrm{\Omega }(A)`$ has dimension 1 if $`\rho _{}=\rho _+`$ and dimension 2 otherwise. If $`A`$ has dense invertible group then so has $`\widehat{A}`$ and we must have $`\rho _{}=\rho _+`$ by Proposition 1.3, as $`A`$ is plainly symmetric.

Conversely suppose that $`\rho _{}=\rho _+`$. Then the spectrum of $`\delta _1`$ has empty interior and Proposition 1.5 applies.

Recall that a uniform algebra, $`A`$, is a Banach subalgebra of $`C(X)`$ with the uniform norm such that $`A`$ separates the points of $`X`$ (a compact Hausdorff space) and contains the constants. A (unital) Banach function algebra satisfies the same axioms as a uniform algebra except that the complete norm on the algebra need not be the uniform norm. The Banach function algebra $`A`$ is called natural if all of its characters are given by evaluation at points of $`X`$ and trivial if $`A=C(X)`$.

In the following result we make use of the Arens-Royden theorem (see for example $`[\mathrm{𝟏𝟗}]`$, p. 411) which implies that whenever $`A`$ is a natural Banach function algebra on a compact Hausdorff space, $`X`$, there is an isomorphism

$$G(A)/e^AG(C(X))/e^{C(X)}$$

and that these groups are isomorphic to the homotopy classes of maps $`XS^1`$. These groups are also isomorphic to $`H^1(X,\mathrm{})`$ the first Čech cohomology group of $`X`$ with coefficients in $`\mathrm{}`$. (Further information about Čech cohomology groups can be found in Section 10 of $`[\mathrm{𝟐𝟑}]`$.) For example when $`X`$ is a compact plane set then $`H^1(X,\mathrm{})=0`$ if and only if $`\mathrm{}X`$ is connected.

THEOREM 1.7. Let $`A`$ be a natural Banach function algebra on a compact Hausdorff space, $`X`$, such that $`H^1(X,\mathrm{})=0`$. Then:

(i) If $`X`$ is locally connected and $`A`$ has dense invertible group then $`A`$ is uniformly dense in $`C(X)`$ (and so trivial if $`A`$ is a uniform algebra).

(ii) If $`X`$ contains a locally connected closed subspace whose topological dimension is at least two then $`A`$ does not have a dense invertible group.

Proof. We prove (ii); one can prove (i) by repeating parts of the argument.

Let $`E`$ be a non-empty, closed, locally connected subspace of $`X`$ of topological dimension at least two and suppose for a contradiction that $`A`$ has a dense invertible group. By the comments above, $`e^A=G(A)`$. Let $`B`$ be the algebra of functions on $`E`$ which are restrictions of elements of $`A`$. Then $`B`$ is isomorphic to the quotient of $`A`$ by the (closed) ideal of functions which vanish on $`E`$. We regard $`B`$ as a Banach function algebra on $`E`$ with respect to this quotient norm.

By hypothesis the set $`=\{fC(E):\text{ there exists }\stackrel{~}{f}e^A\text{ with }\stackrel{~}{f}|_E=f\}`$ is dense in $`B`$. Now let $`C`$ be the closure of $`B`$ in $`C(E)`$. It is easy to check that $`C`$ is a uniform algebra on $`E`$ such that $``$ is dense in $`C`$. Clearly every element in $``$ has a square root in $`C`$ and $`E`$ is locally connected so it follows from Čirka’s theorem (see $`[\mathrm{𝟐𝟑}]`$, p. 131-134) that $`C=C(E)`$. Since $`C(E)`$ has a dense set of invertible elements we must have $`\mathrm{dim}E1`$ by the fundamental result stated in the introduction, a contradiction.

It is a famous open question (see Section 3) whether or not there exists a non-trivial natural uniform algebra on the unit interval, $`I`$. In connection with this we have the following corollary:

COROLLARY 1.8. Let $`A`$ be a natural uniform algebra on the unit interval. If $`A`$ has dense invertible group then $`A=C(I)`$.

Now it follows quite generally and elementarily that elements of $`A\overline{G(A)}`$ have spectra whose interiors contain $`0`$. Thus the set of space-filling curves of a non-trivial natural uniform algebra on the unit interval must have interior in $`A`$. It has certainly been known for a long time ($`[\mathrm{𝟏𝟒}]`$) that every such uniform algebra must contain a function whose image has positive Lebesgue measure. One can also compare the result of Čirka ($`[\mathrm{𝟏𝟓}]`$, p. 670) which shows (using standard theory) that a non-trivial doubly generated natural uniform algebra on $`I`$ must contain a dense set of functions whose images have non-empty interior.

Compare too the above with an unpublished result of Cole ($`[\mathrm{𝟒}]`$) which states that every non-trivial uniform algebra contains a chain of subalgebras $`B_1B_2\mathrm{}`$ such that for each $`n\mathrm{}`$, $`B_n`$ is isomorphic to the $`n`$-dimensional polydisc algebra. We also remind the reader of the well-known examples of (non-natural) uniform algebras $`A`$ on the unit interval such that every non-constant $`fA`$ has the interior of $`f(I)`$ non-empty. (See for example $`[\mathrm{𝟏𝟖}]`$, p. 200.)

The authors would like to thank to Brian Cole and John Wermer for helpful discussions relating to the material in this section.

2. Integral Extensions As hinted at in the introduction denseness of invertible elements in uniform algebras seems to be connected with the existence of roots of monic polynomials over the algebra. Accordingly we mention the following result stated by Grigoryan in $`[\mathrm{𝟏𝟐}]`$: a uniform algebra $`A`$ on a compact space, $`X`$, is trivial if $`C(X)`$ is finitely generated and is an integral extension of $`A`$.

Our main result is that integral extensions of commutative Banach algebras preserve the property of having dense invertible group.

Recall (or see for example p. 369 of $`[\mathrm{𝟏𝟗}]`$) that if $`A`$ is a commutative unital normed algebra and $`\alpha (x)`$ is a monic polynomial over $`A`$ then the Arens-Hoffman extension, $`A_\alpha `$, of $`A`$ by $`\alpha (x)`$ is $`A[x]/\left(\alpha (x)\right)`$ where $`\left(\alpha (x)\right)`$ denotes the principal ideal in $`A[x]`$ generated by $`\alpha (x)`$. There are infinitely many equivalent norms which make this algebra an isometric extension of $`A`$. In fact, for a sufficiently large fixed value of $`t>0`$, such an ‘Arens-Hoffman’ norm is given by

$$\left(\alpha (x)\right)+\beta (x)=\underset{j=0}{\overset{n1}{}}b_jt^j$$

where $`\beta (x)=_{j=0}^{n1}b_jx^j(b_0,\mathrm{},b_{n1}A)`$. (It can be shown, as on p. 128 of $`[\mathrm{𝟏𝟔}]`$ for example, that every element of $`A_\alpha `$ has a unique representative of degree less than $`n`$ so this is well defined.) We shall write $`\overline{x}`$ for the coset $`\left(\alpha (x)\right)+x`$ from now on and we shall assume that the norm on $`A_\alpha `$ is given by an Arens-Hoffman norm.

The proof of our main result relies on resultants; we now recall their definition. Let $`\alpha (x)=a_0+\mathrm{}+a_{n1}x^{n1}+x^n`$ be a monic polynomial over a commutative ring $`A`$ and $`\beta (x)=b_0+b_1x\mathrm{}+b_{n1}x^{n1}A[x]`$. By definition (see for example $`[\mathrm{𝟏𝟔}]`$, p. 325)

$$\mathrm{res}(\alpha (x),\beta (x)):=\left|\begin{array}{cc}\stackrel{n1}{\stackrel{}{\begin{array}{cccc}1& a_{n1}& \mathrm{}& a_2\\ 0& 1& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ 0& \mathrm{}& \mathrm{}& 1\end{array}}}& \stackrel{n}{\stackrel{}{\begin{array}{ccccc}a_1& a_0& 0& \mathrm{}& 0\\ a_2& a_1& a_0& \mathrm{}& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ a_{n1}& a_{n2}& \mathrm{}& \mathrm{}& a_0\end{array}}}\\ \begin{array}{cccc}b_{n1}& b_{n2}& \mathrm{}& b_1\\ 0& b_{n1}& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ 0& 0& \mathrm{}& 0\end{array}& \begin{array}{ccccc}b_0& 0& 0& \mathrm{}& 0\\ b_1& b_0& 0& \mathrm{}& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ b_{n1}& b_{n2}& \mathrm{}& \mathrm{}& b_0\end{array}\end{array}\right|$$

It can be shown (see $`[\mathrm{𝟐}]`$, A.IV §6.6.1) that $`\left(\alpha (x)\right)+\beta (x)`$ is invertible in $`A_\alpha `$ if and only if $`\mathrm{res}(\alpha (x),\beta (x))`$ is invertible in $`A`$.

We see from the above that, writing $`c`$ for $`b_0`$, $`\mathrm{res}(\alpha (x),\beta (x))=P(c)=p_0+p_1c+\mathrm{}+p_{n1}c^{n1}+c^n`$ for some $`p_0,\mathrm{},p_{n1}A`$ which are polynomials in $`b_1,\mathrm{},b_{n1},a_0,\mathrm{},a_{n1}`$ only with coefficients in $`\mathrm{}`$.

We shall usually fix $`\alpha (x)`$ and allow $`\beta (x)`$ to vary. We then denote $`\mathrm{res}(\alpha (x),\beta (x))`$ by $`R_\alpha (\beta (x))`$ for $`\beta (x)A[x]`$.

It is a standard fact ($`[\mathrm{𝟏𝟏}]`$, p. 398) that $`R_\alpha (b_0+\mathrm{}+b_{n1}x^{n1})`$ is homogeneous of degree $`n`$ in $`b_0,\mathrm{},b_{n1}`$ and homogeneous of degree $`n1`$ in $`a_0,\mathrm{},a_{n1},1`$.

Sometimes in the literature (for example $`[\mathrm{𝟑}]`$ and $`[\mathrm{𝟖}]`$) the integral extensions considered are obtained by adjoining square roots. In this case we have $`\alpha (x)=x^2a_0`$ and then $`R_\alpha (b_0+b_1x)=b_0^2a_0b_1^2`$.

THEOREM 2.1. Let $`A`$ be a commutative unital Banach algebra with dense invertible group and $`\alpha (x)`$ a monic polynomial over $`A`$. Then $`G(A_\alpha )`$ is dense in $`A_\alpha `$.

Proof. We may assume $`n2`$. Let $`\beta (x)=b_0+b_1x+\mathrm{}+b_{n1}x^{n1}A[x]`$ and $`\epsilon >0`$. We have to show that there exists $`\stackrel{~}{\beta }(x)A[x]`$ with $`\stackrel{~}{\beta }(\overline{x})\beta (\overline{x})<\epsilon `$ and $`\stackrel{~}{\beta }(\overline{x})G(A_\alpha )`$. In fact we shall show that by slightly perturbing $`b_0`$ only, we can obtain a polynomial $`\stackrel{~}{\beta }(x)`$ with $`R_\alpha (\stackrel{~}{\beta }(x))G(A)`$.

By the above comments, $`P(c)=R_\alpha (c+b_1x+\mathrm{}+b_{n1}x^{n1})`$ is a polynomial $`p_0+\mathrm{}+p_{n1}c^{n1}+c^n`$ where $`p_0,\mathrm{},p_{n1}A`$ are independent of $`c`$. Consider the $`n`$ formal derivatives of $`P`$ as maps $`AA`$:

$$\begin{array}{cc}& P^{(0)}(c)=P(c);\hfill \\ & P^{}(c)=p_1+2p_2c+\mathrm{}+nc^{n1};\hfill \\ & \mathrm{}\hfill \\ & P^{(n1)}(c)=n!c.\hfill \end{array}$$

Set $`\stackrel{~}{c}_{n1}=b_0`$. Note that, trivially, $`P^{(n1)}`$ is a local homeomorphism at $`\stackrel{~}{c}_{n1}`$. Now let $`1k<n`$ and suppose that $`\stackrel{~}{c}_{n1},\mathrm{},\stackrel{~}{c}_{nk}A`$ have been chosen so that

(i) $`P^{(nj)}`$ is a local homeomorphism at $`\stackrel{~}{c}_{nj}(1jk)`$, and

(ii) $`\stackrel{~}{c}_{nj}\stackrel{~}{c}_{n(j1)}<\epsilon /n`$ for $`1<jk`$. We shall now show how to choose $`\stackrel{~}{c}_{n(k+1)}`$ so that (i) and (ii) become true with ‘$`k`$’ replaced by ‘$`k+1`$’.

It is easy to see from the inverse function theorem for Banach spaces (see for example $`[\mathrm{𝟏}]`$, Chapter 7 Theorem 8) that $`P^{(n(k+1))}`$ is a local homeomorphism at $`aA`$ if $`P^{(nk)}(a)`$ is invertible. (This fact is also stated in $`[\mathrm{𝟕}]`$.)

By hypothesis, $`P^{(nk)}`$ is a local homeomorphism at $`\stackrel{~}{c}_{nk}`$ so some open neighbourhood of $`\stackrel{~}{c}_{nk}`$ is mapped onto an open set in $`A`$. Since $`G(A)`$ is dense in $`A`$ there is some $`\stackrel{~}{c}_{n(k+1)}B_A(\stackrel{~}{c}_{nk},\epsilon /n)`$ with $`P^{(nk)}(\stackrel{~}{c}_{n(k+1)})G(A)`$.

Thus $`\stackrel{~}{c}_{n(k+1)}`$ has the required properties and by induction we can choose $`\stackrel{~}{c}_{n1},\mathrm{},\stackrel{~}{c}_0A`$ with $`\stackrel{~}{c}_k\stackrel{~}{c}_{k1}<\epsilon /n(k=1,\mathrm{},n1)`$, $`\stackrel{~}{c}_{n1}=b_0`$, and $`P`$ a local homeomorphism at $`\stackrel{~}{c}_0`$.

Again, since $`P`$ is a local homeomorphism at $`\stackrel{~}{c}_0`$, we can find $`\stackrel{~}{b}_0B_A(\stackrel{~}{c}_0,\epsilon /n)`$ with $`P(\stackrel{~}{b}_0)G(A)`$. Since

$$\stackrel{~}{b}_0b_0\stackrel{~}{b}_0\stackrel{~}{c}_0+\stackrel{~}{c}_0\stackrel{~}{c}_1+\mathrm{}+\stackrel{~}{c}_{n2}\stackrel{~}{c}_{n1}<\epsilon ,$$

the result is proved.

We also remark that the method of proving Theorem 2.1 gives another way to see that if $`A`$ is a commutative unital Banach algebra with $`\overline{G(A)}=A`$ then for every $`n\mathrm{}`$, $`M_n(A)`$ also has dense invertible group. In fact we can approximate any $`B=[b_{ij}]M_n(A)`$ by an invertible matrix by perturbing only $`n`$ entries $`b_{i_1,j_1},\mathrm{},b_{i_n,j_n}`$ provided that $`ki_k,j_k`$ are both permutations. We leave the details to the reader.

COROLLARY 2.2. Let $`A`$ and $`B`$ be commutative normed algebras and suppose that $`B`$ is an integral extension of $`A`$. Suppose that $`A`$ is a full subalgebra of its completion, $`\stackrel{~}{A}`$, and that $`A`$ has dense invertible group. Then $`B`$ has dense invertible group.

Proof. It is sufficient to prove the case when $`B`$ is an Arens-Hoffman extension of $`A`$ for if $`C`$ is a normed integral extension of $`A`$ and $`cA`$ is a root of the monic polynomial $`\alpha (x)A[x]`$ then there is a continuous unital homomorphism $`\theta :A_\alpha C`$ with $`\theta (\overline{x})=c`$; the result quickly follows from this.

Let $`bA_\alpha `$ and let $`\epsilon >0`$. It is not hard to show that the universal property of Arens-Hoffman extensions which has just been mentioned allows us to identify $`(\stackrel{~}{A})_\alpha `$ with $`\stackrel{~}{A_\alpha }`$. By Theorem 2.1 there exists $`b{}_{}{}^{}G((\stackrel{~}{A})_\alpha )`$ with $`b^{}b<\epsilon /2`$. Suppose $`b^{}=_{k=0}^{n1}b_k^{}\overline{x}^k`$ where $`n`$ is the degree of $`\alpha (x)`$ and $`b_0^{},\mathrm{},b_{n1}^{}\stackrel{~}{A}`$. Since $`G((\stackrel{~}{A})_\alpha )`$ is open (the Arens-Hoffman extension of a Banach algebra is complete) we can perturb $`b_0^{},\mathrm{},b_{n1}^{}`$ to obtain $`b_0^{\prime \prime },\mathrm{},b_{n1}^{\prime \prime }A`$ so that $`b^{\prime \prime }=_{k=0}^{n1}b_{}^{}{}_{k}{}^{}\overline{x}^k`$ is invertible in $`(\stackrel{~}{A})_\alpha `$ and $`b^{\prime \prime }b^{}<\epsilon /2`$. But now $`R_\alpha (b^{\prime \prime })G(\stackrel{~}{A})A=G(A)`$ so $`b^{\prime \prime }`$ is invertible in $`A_\alpha `$ and $`b^{\prime \prime }b<\epsilon `$.

The following theorem follows directly from this corollary:

THEOREM 2.3. Let $`B`$ be a commutative Banach algebra which is an integral extension of the commutative Banach algebra $`A`$. If $`A`$ has dense invertible group then so has $`B`$.

The converse of Theorem 2.1 seems harder to investigate. However the method of the proof gives at least partial information in this direction:

PROPOSITION 2.4. Suppose that $`A`$ is a commutative unital Banach algebra and $`\alpha (x)`$ is a monic polynomial of degree $`n`$ over $`A`$. If $`A_\alpha `$ has dense invertible group then $`\{bA:\text{there exists }aA\text{ such that }b=a^n\}`$, the set of $`n`$th powers, is contained in the closure of $`G(A)`$.

Proof. Fix $`aA`$ and let $`\epsilon >0`$. Let the norm parameter for the Arens-Hoffman extension be $`t>0`$. Then there exists $`\beta _\epsilon (x)=b_{\epsilon ,0}+\mathrm{}+b_{\epsilon ,n1}x^{n1}A[x]`$ such $`R_\alpha (\beta _\epsilon (x))G(A)`$ and

$$\beta _\epsilon (x)a=b_{\epsilon ,0}a+\underset{j=1}{\overset{n1}{}}b_{\epsilon ,j}t^j<\epsilon .$$

Now as we mentioned before, $`R_\alpha (b_0+\mathrm{}+b_{n1}x^{n1})`$ is homogeneous of degree $`n`$ in $`b_0,\mathrm{},b_{n1}`$. Therefore, writing $`R_\alpha (\beta (x))=P(b_0)=_{j=0}^{n1}p_jb_0^j+b_0^n`$ as in Theorem 2.1, we have that each coefficient $`p_j(j=0,\mathrm{},n1)`$ is a sum of elements of $`A`$ each of which has $`b_k`$ as a factor for some $`k\{1,\mathrm{},n1\}`$.

Thus, letting $`\epsilon 0`$, we obtain invertible elements $`R_\alpha (\beta _\epsilon (x))`$ in $`A`$ which tend to $`a^n`$.

It is clear that the property of having a dense invertible group passes to quotients and completions of normed algebras. The following is also clear.

PROPOSITION 2.5. Let $`A`$ be a direct limit of normed algebras with dense invertible groups and where the connecting homomorphisms are unital isometric monomorphisms. Then $`A`$ has dense invertible group.

Proof. This is clear.

We mention the consequences of these results for some of the examples of uniform algebras constructed by Karahanjan, Cole, and Feinstein ($`[\mathrm{𝟏𝟕}]`$, $`[\mathrm{𝟑}]`$, $`[\mathrm{𝟖}]`$). Specifically we are referring to those obtained by taking Banach algebra direct limits of systems of uniform algebras in which the intermediate algebras are completions (or quotients followed by completions) of algebraic extensions of their predecessors. In many of these the initial algebra has dense invertible group and so the final algebra also has this property. In particular our results show that there is no need to invoke the theory of ‘dense thin systems’ as developed in $`[\mathrm{𝟏𝟕}]`$.

3. Open Questions

1. The question of whether or not there is more than one natural uniform algebra on the unit interval is now about fifty years old. It seems to have been first formally asked by Gelfand in 1957 ($`[\mathrm{𝟏𝟎}]`$). The answer is not known even if we assume that the algebra is regular. See $`[\mathrm{𝟗}]`$ and the references cited there for material on this problem.

2. Let $`A`$ be a commutative Banach algebra with maximal ideal space $`\mathrm{\Omega }`$ and Šilov boundary $`S`$. A lack of examples describing $`\overline{G(A)}`$ leads to the following conjectures:

(a) If $`\overline{G(A)}=A`$ then $`S=\mathrm{\Omega }`$.

(b) If $`\overline{G(A)}=A`$ then $`C(\mathrm{\Omega })`$ has dense invertible group.

(c) If $`S=\mathrm{\Omega }`$ and the invertible elements of $`C(\mathrm{\Omega })`$ are dense in $`C(\mathrm{\Omega })`$ then $`\overline{G(A)}=A`$.

It follows from standard properties about the maximal ideal space and Šilov boundary of the uniform closure of a Banach function algebra (see for example $`[\mathrm{𝟔}]`$, p. 447) that we may assume $`A`$ is a uniform algebra in Questions 2(a) and 2(b). The answer to 2(c) may depend on the category.

3. The converse of Theorem 2.1 remains open.

4. We do not know if the word ‘full’ is redundant in Corollary 2.2.

References

$`[\mathrm{𝟏}]`$ Bollobás, B. (1999): ‘Linear Analysis’, 2nd edition, Cambridge: Cambridge University Press.

$`[\mathrm{𝟐}]`$ Bourbaki, N. (1988) ‘Algebra II, Chapters 4-7’, US: Springer-Verlag.

$`[\mathrm{𝟑}]`$ Cole, B. J. (1968): ‘One-Point Parts and the Peak Point Conjecture’, PhD Thesis, Yale University.

$`[\mathrm{𝟒}]`$ Cole, B. J. (2002): Private communication.

$`[\mathrm{𝟓}]`$ Corach, G. and Suárez, F. D. (1988): ‘Thin Spectra and Stable Range Conditions’, J. Funct. Anal., 81, 432-442.

$`[\mathrm{𝟔}]`$ Dales, H. G. (2001): ‘Banach Algebras and Automatic Continuity’, New York: Oxford University Press Inc.

$`[\mathrm{𝟕}]`$ Falcón-Rodríguez, C. M. (1988) ‘Sobre la densidad del grupo de los elementos invertibles de un álgebra uniforme’, Revista Ciencias Matemáticas, IX, no. 2, 11-17.

$`[\mathrm{𝟖}]`$ Feinstein, J. F. (1992): ‘A Non-Trivial, Strongly Regular Uniform Algebra’, J. Lond. Math. Soc., 45, no. 2, 288-300.

$`[\mathrm{𝟗}]`$ Feinstein, J. F. and Somerset, D. W. B. (1999): ‘Strong Regularity for Uniform Algebras’, Contemp. Math., 232, 139-149.

$`[\mathrm{𝟏𝟎}]`$ Gelfand, I. M. (1957): ‘On the Subrings of a Ring of Continuous Functions’, Usp. Mat. Nauk, 12, no. 1, 249-251.

$`[\mathrm{𝟏𝟏}]`$ Gelfand, I. M., Kapranov, M. M., and Zelevinsky, A. V. (1994) ‘Discriminants, Resultants, and Multidimensional Determinants’, United States of America: Birkhäuser Boston.

$`[\mathrm{𝟏𝟐}]`$ Grigoryan, S. A. (1984): ‘Polynomial Extensions of Commutative Banach Algebras’, Russian Math. Surveys, 39, no. 1, 161-162.

$`[\mathrm{𝟏𝟑}]`$ Hatori, O. and Miura, T.: (1999) ‘On a Characterization of the Maximal Ideal Spaces of Commutative $`C^{}`$-Algebras in which Every Element is the Square of Another’, Proc. Am. Math. Soc., 128, no. 4, 1185-1189.

$`[\mathrm{𝟏𝟒}]`$ Helson, H. and Quigley, F. (1957): ‘Existence of Maximal Ideals in Algebras of Continuous Functions’, Proc. Am. Math. Soc., 8, 115-119.

$`[\mathrm{𝟏𝟓}]`$ Henkin, G. M. and Čirka, E. M. (1976): ‘Boundary Properties of Holomorphic Functions of Several Complex Variables’, J. Soviet Math., 5, no. 5, 612-687.

$`[\mathrm{𝟏𝟔}]`$ Jacobson, N. (1996) ‘Basic Algebra I’ (2nd ed.) New York: W. H. Freeman and Company.

$`[\mathrm{𝟏𝟕}]`$ Karahanjan, M. I. (1979): ‘Some algebraic characterizations of the algebra of all continuous functions on a locally connected compactum’, Math. USSR Sb., 35, 681-696.

$`[\mathrm{𝟏𝟖}]`$ Leibowitz, G. M. (1970) ‘Lectures on Complex Function Algebras’, United States of America: Scott, Foresman and Company.

$`[\mathrm{𝟏𝟗}]`$ Palmer, T. W. (1994) ‘Banach Algebras and the General Theory of \*-Algebras’ (vol. 1), Cambridge: CUP.

$`[\mathrm{𝟐𝟎}]`$ Pears, A. R. (1975) ‘Dimension Theory of General Spaces’, Cambridge: CUP.

$`[\mathrm{𝟐𝟏}]`$ Rieffel M. A. (1983): ‘Dimension and Stable Rank in $`K`$-Theory of $`C^{}`$-Algebras’, Proc. Lond. Math. Soc., 46, no. 3, 577-600.

$`[\mathrm{𝟐𝟐}]`$ Robertson, G. (1976): ‘On the Density of the Invertible Group in $`C^{}`$-Algebras’, Proc. Edinb. Math. Soc., 20, 153-157.

$`[\mathrm{𝟐𝟑}]`$ Stout, E. L. (1973) ‘The Theory of Uniform Algebras’, Tarrytown-on-Hudson, New York: Bogden and Quigley Inc.

T. W. Dawson

E-mail: pmxtwd@nottingham.ac.uk

Dr. J. F. Feinstein

E-mail: Joel.Feinstein@nottingham.ac.uk

Division of Pure Mathematics,

School of Mathematical Sciences,

University of Nottingham,

University Park,

Nottingham,

NG7 2RD,

UK.