Augustin Habran -

Daniel K Richter

Donald L Fixico

Indianness and Democracy: Andrew Jackson's "big problem"

Andrew Jackson's coming to power as the president of the United States in 1828 constituted a major turning point regarding federal Indian policy. Jackson's radicalism, that reached its peak with the deportation of Indian populations living east of the Mississippi to present-day Oklahoma, forced Native American nations to develop strategies of resistance. Among the southeastern nations, resistance imposed the strategic use of cultural transformation and the redefinition of Indianness to try and maintain Indian sovereignty on ancestral lands. The following paper examines the ways both Andrew Jackson and Indian leaders appropriated and articulated the tenets of American Democracy to fuel their antagonistic agendas.

Apprehending the full scope of Native American history and realities during the socalled Jacksonian era is a difficult endeavor. Not only is it a time of radical Federal and local actions against Native Americans whose ancestral territories were located east of the Mississippi, and a period that was characterized by dispossession, cultural genocide, and deadly deportation, but it is also a complex ideological and political turning point. It imposes a fundamental reflection on the part Indian nations were meant to play -or rather not to play -in the continental affirmation of American Democracy in the middle of the 19 th century. Besides, it demands the paradox of Jacksonian ideology be analyzed. The radicalism of the period, that Jackson embodied in the most outstandingly populist and somehow "tyrannical" manner, is expressed through the federal policy developed at the time to solve what came to be known as the "Indian problem". That is why, with regards to the question addressed here, one needs to examine how Jackson apprehended the very notion of democracy -and distorted it -and the way he used the republican apparatus to complete, as the head of the executive, the long-term anti-Indian agenda he had nurtured ever since his young years as a Frontiersman.

Historiography has taught us that the thorough analysis of the Native American perspectivethe "facing east" analysis -was substantial to fully understand the cultural, political and ideological dynamics at play in the period 1 . Needless to say the development of American 1 The methodology of ethnohistory, developed in the wake of the New Indian History in the 1990s, has allowed for a reconsideration of the dynamics at stake in the construction of colonial North America. It has notably highlighted Native American agency and perspectives.

Democracy relies on colonization. Besides the colonial and national incentives behind the founding of the American Nation-State, the establishment and expansion of the early American republic was a function of Native American agency, that is to say Indian initiatives -mainly of adaptation to settler colonialism, resilience and resistance. Indian presence and actions were an "obstacle" the American republic had to deal with from the start. While territorial expansion depended on constant negotiation and often violent physical interactions between colonists and indigenous populations, the ideological process of self-definition and continental appropriation of the United States implied the othering of Native American cultures, a phenomenon that legitimized Euro-American occupation of American soil and highlighted the incompatibility of Indians with the rising democracy at the same time. As American Republican Democracy was perceived as natural, providential, and a synonym to human progress and civilization, it came as "self-evident" that Indians had to be neutralized, whether through annihilation, removal or forced assimilation. In the meantime, as they were imposed intercultural interactions, Indian populations had to adapt to this ever-growing colonial sphere that legitimized the appropriation of land first because of culture, then because of race. This led to more-or-less conscious cultural transformations among Native nations that underwent acculturation, mostly through trade. The evolutions of social and political organizations of these nations helped maintain integrity and self-determination -in one word: sovereignty -. In the process, Native Americans came to apprehend their own Indianness and shaped it repeatedly in order to resist American expansion while trying as hard as possible to keep the essence of their identity on the lands on which tribal cohesion had always depended. As he took office in 1828, Andrew Jackson was confronted to a striking reality: the Indian nations his anti-Indian policy targeted defied the colonial dichotomy between "civilization" and "savagism" that justified the inferiority of indigenous populations. Despite the treaties signed before the War of 1812 and the cessions imposed by the Treaty of Fort Jackson in 1814 in the Deep South, the southeastern nations (namely the Choctaws, Chickasaws, Creeks and Cherokees) still owned important tracts of land and constituted an obstacle to the expansion of the Slave South. Most importantly, as they had to resist the land-greedy settlers of Georgia and South Carolina, that had been promised the extinction of Indian sovereignty by Thomas Jefferson as early as 1802 (Compact of 1802), these Indian nations had strategically reshaped their own Indianness. Thus, under the influence of a mixed-blood political and economic elite that had emerged within the nations during the colonial era, these nations had transformed their cultural and political organizations to fit in the developing American Republic. In building "civilized" agricultural and slave societies in the South-East, and establishing constitutional republican governments, the leaders of these nations had managed to use acculturation as a means to resist American expansion using the cultural and legal tenets of American Democracy. That was indeed Jackson's big "problem". In this paper, I will first study the way Jackson used the growth of the anti-Indian feeling and the rise of pseudo-scientific racism, nationalism, and imperialism in the 1820s as a rationale for his southern-oriented plan of Indian deportation. I will then examine the strategies of resistance developed by the southeastern nations in this context of radicalization in the South, and the populist and authoritarian distortions of the democratic ideology Jackson operated to achieve the complete subjugation of Indians east of the Mississippi River.

I-Indianness and democracy: incompatibility reaffirmed in the 1820s

From 1824 to 1848, Federal Indian policies targeted more specifically the southeastern Indian nations -the so-called "Five Civilized Tribes". On the one hand, most of Indian populations in the Old North-West had been annihilated under Jefferson's presidency. On the other hand, the southeastern nations still occupied important territories that overlapped the territories of the new states founded after the War of 1812 (Mississippi in 1817, and Alabama in 1819 for instance). Most importantly, these nations had been involved in the conflict with Great Britain, that had turned into an Indian civil war in the South because of the Red Stick rebellion that had eventually been destroyed by Jackson's troops and their Indian allies. In the South, Indians came to be seen as enemies from within, populations that represented a danger to the Union and a constant threat to the populations of settlers that had established in the backcountry. The years that followed the victory over the British marked the renewal of American nationalism and the emergence of a strong expansionist momentum in the South-East. Jackson, who had become a national hero for his actions during the war, launched a military campaign to secure the Frontier and guarantee the protection of southern settlers that, according to him, had be abandoned by the Federal government. His bold actions, the most daring of which was the invasion and imposition of martial law in Spanish Florida in 1818 to "strike the wolf in his den" -as he wrote to John Calhoun in 1817 referring to rebel Indians that had taken refuge among the Seminoles of Florida -galvanized southern settlers who were growing impatient to see the federal government act and remove the Indian "hindrance" to the irresistible expansion of "civilization" over the "wilderness". In the meantime, the growing white population in the westernmost territories that enjoyed recent universal suffrage, the economic weight of these regions due to the boom of the King Cotton, and the presence of influential southern political figures such as John Calhoun in the federal executive eventually made "Frontier issues" national issues.

The emergence of the "Indian problem" must be studied through the lens of the growing racialization of American society in the 1820s. As Charles Caldwell and Samuel George Morton theorized racial polygenesis, the rise of pseudo-scientific racism provided southern settlers with the perfect justification for racial segregation and the extinction of Indian sovereignty. Meanwhile, southern politicians led by Jackson's rising national aura demanded quick actions be taken by the Federal government. Jackson, who had always advocated for the end of treaty-making diplomacy, found an outstanding echo in those impatient populations.

What is more, to him, Indians were to be subjects of the republic, and Indian nations -that had been considered as independent sovereign nations so far -had to be denied their right to selfdetermination.

In the wake of pseudo-scientific racism, the thesis of the "vanishing Indian" also developed and gained popular appeal. Not only did their "racial and physical difference" prevented the Indians from enjoying the "blessings of civilization" (defined at the time by Christianity, individual property, and the extensive exploitation of land), their incompatibility with democracy and progress also caused their "degradation". This would undeniably lead to their extinction. "They have […] ceased to be an object of terror, and have become that of commiseration", Calhoun affirmed in his report on the system of Indian Trade in 1818, pointing out their dependence and submission to white civilization and trade. This pathetic vision of contemporary Indian populations living east of the Mississippi pervaded American society as a whole. Politicians, including Jackson's Whig opponent Henry Clay, affirmed that progress was impossible for Indians to achieve because of their race. French observer Alexis de Tocqueville mentioned the "remnants of indigenous populations" he encountered. Literary figures and intellectuals also developed the idea that the Indians were about to disappear. James Fenimore

Cooper's The Last of the Mohicans -one of Jackson's bedside readings -was published in 1826.

Politically, if the thesis of "degradation" pushed some activists and social reformers to question the federal Indian policy, it mostly reinforced the idea that Indians living east of the Mississippi had to be removed farther west. The project of relocating Eastern Indians to the regions described at the time as the "Great American Desert" by Stephen H. Long was not new.

Jefferson, after the Louisiana Purchase in 1803, had already envisioned Indian removal as an alternative to assimilation: "They will in time either incorporate with us as citizens of the US or remove beyond the Mississippi", he wrote in a letter to William Henry Harrison. Still, incitement to remove the Indians increased in the 1820s. Interestingly, the alleged "degradation" of Indians added a supposedly humanist tone to the project of deportation.

Advocates of the new colonization such as Jedediah Morse and Isaac McCoy insisted on the fact that relocation was supposed to avoid the extermination of Indians and "promote their welfare, happiness and future progress". The American Colonization Society founded in 1816, that created Liberia in 1821 to relocate Free Blacks to Africa with the same arguments, campaigned actively in favor of this policy of dispossession that ended up being perceived by a majority as a benevolent one 2 . Quite logically, Andrew Jackson embraced the removal project completely. He made it the centerpiece of his presidential platform in 1828 and Indian Removal remains his most outstanding "legacy". In affirming that removal would "enable [Indians] to pursue happiness in their own way", "retard their decay" and allow them "to cast off their savage habits and become an interesting, civilized and Christian community", Jackson strategically used the philanthropic argument developed at the time, hypocritically associated deportation with democratic ideals of opportunity and happiness and opened the way to the capitalist interests of the Slave South in one fell swoop. Strikingly enough, in opposition to his predecessors (including John Quincy Adams), Jackson insisted on the fact that removal should be forced upon the Indians. Using authority -if not "tyranny" -to implement the deportation of Eastern Indians despite considerable opposition in Congress but also in civil society, Jackson adamantly reaffirmed Indian incompatibility with civilized democracy and called for strong actions in the name of the legitimate "good people" of the republic. Relying on racist arguments coated with benevolence, Jackson strategically ignored the cultural transformations undergone by the southeastern nations. The latter were not the "few savage hunters" that he described in his message to Congress in December 1830. Activists, missionaries, and opponents to removal pointed out a completely different reality to prevent forced deportation. In 1829, the Cherokees themselves affirmed they had "unexpectedly become civilized". Jackson knew it too well. It was an argument he was not willing to consider.

II-Transforming Indianness to survive: acculturation as resistance

At the beginning of the 19 th century, the southeastern nations constituted an exception in the North American Native landscape. Ever since the colonial era, these descendants of the formerly powerful mound-building Mississippian civilization had seen their culture evolve due 2 Nicholas Guyatt, ""The Outskirts of Our Happiness": Race and the Lure of Colonization in the Early Republic",

The Journal of American History 95, n o 4 (2009): 986-1011.

to the intense diplomatic and commercial interactions they had engaged in with British, French and Spanish colonists on a particularly volatile contact zone 3 . As the agricultural character of these sedentary matrilinear societies allowed for the establishment of trading posts and development of extensive trade, the integration of white merchants within the indigenous populations led to the appearance of a mixed-blood elite that, at the end of the 18 th century, took over economic and political control of the nations and favored outstanding acculturation, from the integration of European goods and tools to the adoption of Black slavery. That cultural specificity favored their participation as agents in the construction of the South-East and delayed, to some extent, the loss of land and sovereignty for a while. Also, the southeastern nations that, in opposition to northeastern nations, chose accommodation to survive the colonial purpose of removing nation after nation of them from the lands of their fathers". On the surface, Indian leaders aimed at satisfying the federal will to see the Indians assimilate and "disappear"

in showing evidence of a cultural and moral ability to adapt while responding, in depth, to tribal and national objectives to preserve territorial sovereignty. The state-like entities developed by the nations in the South-East, framed by laws and constitutions (especially in the case of the Cherokees, that drafted a constitution in 1827) that defined Indian territory in the law, allowed Indian nations to resist expansion using Euro-American legal language and tools that could have left no choice to the Federal and local states but to acknowledge Indian legitimacy.

Indianness was reshaped so that tribal integrity could be maintained using the very tenets of then-developing American Democracy. On March 4, 1829, an address intitled "To the Cherokee

People" in the Cherokee Phoenix, first Native American newspaper to be published written both in English and Cherokee language, stated: "We have noticed the ancient ground of complaint founded on the ignorance of our ancestors and their fondness of the chase, and for the purposes of agriculture as having in possession too much land for their numbers. What is the language of objection at this time? The case is reversed, and we are now assaulted with menaces of expulsion because we have unexpectedly become civilized. We have formed and organized a constitutional government". As if to contradict an American society that believed they were doomed to extinction, the southeastern nations surprised the Federal government with the establishment of a state-making apparatus. It allowed them to assert their legitimacy to occupy their territory to the Supreme Court as a nation against the State of Georgia that had imposed its jurisdiction on the Cherokee nation independently from the Federal government in 1828. In 1832, the Supreme Court led by Chief Justice Marshall made a ruling of the Worcester v. Georgia case. It stated that states did not have the right to impose regulations on Native American land. President Jackson refused to enforce the ruling. "Let him enforce it!" he is said to have declared, keeping up with the populist and constitutionally ambiguous political attitude that had him elected president with more than 90% of popular vote in Georgia and Tennessee.

III-Distorting democracy: populism in power

From the early 1820s, as he rose to the status of national political figure, first as governor of Florida where he forced the Seminoles onto a reservation with the treaty of Moultrie Creek in 1823, then as the unlucky presidential candidate of 1824, Jackson understood his anti-Indian rhetoric and defense of slavery appealed to the settlers of the Frontier. He knew the progressive democratization of the backcountry would favor the political emergence of the Frontier states and he aimed at becoming their ideological representative. Jackson made his own the growing sectionalism of the Slave South that rested upon the idea that the Federal government did not accompany local initiatives of popular expansionism against Indian sovereignty. As he claimed to represent the "common people" he described as "the planter, the farmer, the mechanic and the plowman" who "love liberty and desire nothing else but equal rights" against established and corrupt National Republican elites in Washington, Jackson developed a populist discourse 5 .

He appropriated the Jeffersonian democratic ideology that favored states' rights in the fight against Indian sovereignty. In the name of the "common man", of republican virtue and in camps and deported to the West by the US army. The sadly famous Trail of Tears, that took place from 1838 and was implemented by Jackson's ideological heir, Martin Van Buren, caused the death of at least 4,000 Cherokees. Women, men and children had to undergo deportation on foot through nine states to reach allocated lands in Indian Territory. They faced cold, starvation and diseases. Some babies were even killed by members of the army for they were a "burden" that slowed down migration. We usually mention the deportation of the so-called "Five Civilized Tribes", but one needs to remember that the whole of eastern Indian populations suffered the same uprooting. From the Black Hawk War in 1832 to the Second War with the Seminoles (1835-1842) stem the respective exiles of the Sauk and Fox and the Seminoles.

About 80,000 people were removed from their homes in what may be considered as one of the first mass deportation in the modern world. Some even argue that the conditions in which Indians were deported make removal a case of actual genocide. As they were forcibly removed, the southeastern nations, that were considered as "domestic dependent nations" since the Supreme Court decision of 1831 in the Georgia v. Cherokee Nation legal case, had to reinvent new forms of sovereignty in the Great Plains, on the lands allocated by the State that actually belonged to Plains Indians. While trying to rebuild national unity in Indian Territory, the deported nations became "civilized" and slave-owning agents of the construction of a disputed West, at a time when Manifest Destiny pushed American settlers to rush to the Pacific.

  invasion, were particularly receptive to the Civilization Program implemented by Jefferson who planned to make Indians farmers of the agrarian republic. Access to individual property would lead the Indians to abandon the large hunting grounds they still owned; assimilation would make the Indian obstacle "vanish". Philosophically, the Federal government would avoid extermination; technically, the American Republic would expand. As far as the Indian populations were concerned, agricultural development, the integration into the southern market economy and the success of what federal authorities considered as evidence of a civilizing process, allowed for a limitation of colonial invasion on their lands.Yet, the consequences of the Creek War, the emergence of the anti-Indian ideology and the growing pressure exerted on them by backcountry settlers in the 1820s pushed the southeastern nations to reconsider their strategies of resistance. Still under the influence of the mixed-blood elite that favored acculturation, as they went from an oral tradition to a written tradition (especially among the Cherokees where Sequoyah had invented an alphabet), the nations developed what I contend to be a form of "strategic mimesis" 4 . Reinforced acculturationcharacterized by ideological connections with the colonial South through the development of the Peculiar Institution and the industrialization of agriculture for instance -was supposed to counter the idea that Indians were not compatible with civilization and delay the attacks Indian sovereignty constantly underwent. Cherokee chief John Ross affirmed in 1822 that "when the Indians are seen themselves to manifest the will to reach the blessings and happiness derived of civilized life" he could not "believe that the United States would continue […] to effect the 3 Daniel Walker Howe, What Hath God Wrought: The Transformation of America, 1815-1848, New York: Oxford University Press, 2007, p.28. 4 William G. McLoughlin refers to this period as "Cherokee Renascence". William G. McLoughlin, Cherokee Renascence in the New Republic, Princeton: Princeton University Press, 1986.

  patriotism, he legitimized what Matthew Karp recently referred to as a "vast southern empire" that relied on slavery and served purely capitalist interests at the time of the "market revolution" 6 . It also justified the invasion of Indian lands by southern settlers, emboldened by Jackson's repeated constitutional infringements like in Florida. From 1827 to 1833, Georgia, Tennessee, Alabama and Mississippi unilaterally decided to impose their jurisdictions on Indian nations and settlers started to invade Indian territories systematically. That was Jacksonian ideology at work. Historian Claudio Saunt has recently contended that removal could have been avoided if it had not been for Jackson's autocratic power 7 .Still, Eastern Indians were given an impossible choice: they could keep their sovereignty, but they could not keep their land. As death was coming to Indian lands, many Indian leaders decided to voluntarily leave. They accepted to sign federal treaties in the 1830s and endured removal as a means of maintaining the tribal nations. Those who resisted were eventually put

	5 Harry L. Watson, "Andrew Jackson's Populism", Tennessee Historical Quarterly 76, n°3 (2017): 218-239.

On May 28, 1830, the Indian Removal Act was voted in Congress, implementing the forced relocation of all eastern Indian populations to present-day Oklahoma. It would be wrong to underestimate the opposition to the deportation of Indians. While Native American leaders multiplied diplomatic visits to Washington to appeal this radical decision, intellectuals, missionaries, abolitionists, and feminist activists including Catharine Beecher, Jeremiah Evarts and Samuel Worcester campaigned in favor of the Indians. The Whigs somehow opposed Indian Removal, mostly to condemn what they considered to be "tyranny". "Will the American government steal? Will it lie? Will it kill?", Emerson exclaimed at the time. After all, the vote in Congress was close (101 for, 97 against). 6 Matthew Karp, The Vast Southern Empire: Slaveholders at the Helm of American Foreign Policy, Cambridge: Harvard University Press, 2016. 7 Claudio Saunt, "Unworthy Republic": The Dispossession of Native Americans and the Road to Indian Territory, New York: WW Norton, 2020.


Monique Laurent
email: m.laurent@cwi.nl

Bernard Mourrain
email: mourrain@sophia.inria.fr

A SPARSE FLAT EXTENSION THEOREM FOR MOMENT MATRICES

Keywords: 1991 Mathematics Subject Classification. Primary 30E05; Secondary 12D10 Truncated moment problem, moment matrix, Hankel operator, polynomial optimization

In this note we prove a generalization of the flat extension theorem of Curto and Fialkow [4] for truncated moment matrices. It applies to moment matrices indexed by an arbitrary set of monomials and its border, assuming that this set is connected to 1. When formulated in a basis-free setting, this gives an equivalent result for truncated Hankel operators.

Introduction

Throughout this note, K denotes a field, K[x] = K[x 1 , . . . , x n ] is the ring of multivariate polynomials in n variables x = (x 1 , . . . , x n ) with coefficients in K,

M n = {x α := x α1 1 • • • x αn n | α ∈ N n }
is the set of monomials in the variables x, and M n,t (resp., K[x] t ) is the set of monomials (resp., of polynomials) of degree at most t. The dual basis of M n in the dual space K[x] * is denoted as

D n = {d β | β ∈ N n }. The natural action of K[x] on K[x] * is denoted by (p, Λ) ∈ K[x] × K[x] * → p • Λ ∈ K[x] *
where (p • Λ)(q) := Λ(pq) for q ∈ K[x].

1.1. The moment problem. In this section, we consider K = R. The moment problem (see e.g. [START_REF] Akhiezer | The Classical Moment Problem[END_REF][START_REF] Fuglede | The multidimensional moment problem[END_REF]) deals with the characterization of the sequences of moments of measures. Given a probability measure µ on R n , its moment of order a = x α ∈ M n is the quantity x α µ(dx). The moment problem concerns the characterization of the sequences y = (y a ) a∈Mn that are the sequences of moments of some nonnegative measure µ, in which case one says that µ is a representing measure for y, with y 1 = 1 if µ is a probability measure. Let Λ ∈ R[x] * denote the linear form on R[x] associated to the sequence y, defined by Λ(p) = a p a y a for any polynomial p = a∈Mn p a a ∈ R[x]. Then, y has a representing measure µ precisely when Λ is given by Λ(p) = p(x)µ(dx) for all p ∈ R[x]. A well known necessary condition for the existence of a representing measure is the positivity of Λ, i.e. Λ(p 2 ) ≥ 0 for all p ∈ R[x], which is equivalent to requiring that the matrix M (y) := (y ab ) a,b∈Mn be positive semidefinite. As is well known this necessary condition is also sufficient in the univariate case (n = 1) (Hamburger's theorem), but it is not sufficient in the multivariate case (n ≥ 2). However, positivity is sufficient for the existence of a representing measure under some additional assumptions. This is the case, for instance, when the sequence y is bounded [START_REF] Berg | Positive definite functions on Abelian semigroups[END_REF] or, more generally, exponentially bounded [START_REF] Berg | Exponentially bounded positive definite functions[END_REF]. The next result of Curto and Fialkow [START_REF] Curto | Solution of the truncated complex moment problem for flat data[END_REF] shows that this is also the case when the matrix M (y) has finite rank (cf. also [START_REF] Laurent | Revisiting two theorems of Curto and Fialkow on moment matrices[END_REF][START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF] for a short proof).

Theorem 1.1. [START_REF] Curto | Solution of the truncated complex moment problem for flat data[END_REF] If M (y) is positive semidefinite and the rank of M (y) is finite, then y has a (unique) representing measure (which is finitely atomic with rank M (y) atoms).

In the univariate case n = 1, a matrix of the form M (y) is a Hankel matrix. In the multivariate case, M (y) is known as a generalized Hankel matrix (see [START_REF] Mourrain | Multivariate Polynomials, Duality, and Structured Matrices[END_REF]) or moment matrix (see [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF]). One can also define truncated moment matrices: A matrix When C = M n,t , we also write M = M t (y), where the entries of y are indexed by M n,2t . Such matrices arise naturally in the context of the truncated moment problem, which asks for the existence of a representing measure for a truncated sequence indexed by a subset of monomials. A solution to the truncated moment problem would in fact imply a solution to the moment problem. Indeed, Stochel [START_REF] Stochel | Solving the truncated moment problem solves the moment problem[END_REF] shows that a sequence y = (y a ) a∈Mn has a representing measure if and only if the truncated sequence (y a ) a∈Mn,t has a representing measure for all t ∈ N.

M indexed by a subset C ⊆ M n is said to be a moment matrix if M a,b = M a ′ ,b ′ for all a, b, a ′ , b ′ ∈ C with ab = a ′ b ′ . Thus
1.2. The flat extension theorem of Curto and Fialkow. Curto and Fialkow studied intensively the truncated moment problem (cf. e.g. [START_REF] Curto | Solution of the truncated complex moment problem for flat data[END_REF][START_REF] Curto | Flat extensions of positive moment matrices: recursively generated relations[END_REF][START_REF] Curto | The truncated complex K-moment problem[END_REF] and further references therein). In particular, they observed that the notion of flat extension of matrices plays a central role in this problem. Given matrices M C and M B indexed, respectively, by C and B ⊆ C, M C is said to be a flat extension of M B if M B coincides with the principal submatrix of M C indexed by B and rank M C = rank M B . Curto and Fialkow [START_REF] Curto | Solution of the truncated complex moment problem for flat data[END_REF] show the following result for truncated moment matrices.

Theorem 1.2 (The flat extension theorem [START_REF] Curto | Solution of the truncated complex moment problem for flat data[END_REF]). For a sequence y = (y a ) a∈Mn,2t , if M t (y) is a flat extension of M t-1 (y), then there exists a (unique) sequence ỹ = (ỹ a ) a∈Mn for which M (ỹ) is a flat extension of M t (y).

The flat extension theorem combined with Theorem 1.1 directly implies the following sufficient condition for existence of a representing measure.

Corollary 1.3. For a sequence y = (y a ) a∈Mn,2t , if M t (y) is positive semidefinite and M t (y) is a flat extension of M t-1 (y), then y has a representing measure. [START_REF] Curto | Flat extensions of positive moment matrices: recursively generated relations[END_REF] show moreover that the flat extension condition is in some sense necessary and sufficient for the existence of a representing measure. More precisely, they show that a sequence y = (y a ) a∈Mn,2t has a representing measure if and only if it can be extended to a sequence y ′ = (y ′ a ) a∈M n,2t+2k+2 (for some k ≥ 0) for which M t+k+1 (y ′ ) is a flat extension of M t+k (y ′ ).

Curto and Fialkow

The proof of Theorem 1.2 relies on a "truncated ideal like" property of the kernel of flat moment matrices (see (2.2) below). This permits to set up a linear system of equations in order to construct the flat extension M t+1 (ỹ) of M t (y) (and then iteratively the infinite flat extension M (ỹ)). See also [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF] for an exposition of this proof. Schweighofer [START_REF] Schweighofer | A Gröbner basis proof of the flat extension theorem for moment matrices[END_REF] proposes an alternative proof which is less technical and relies on properties of Gröbner bases. We propose in this note another simple alternative proof, which applies more generally to truncated moment matrices indexed by (suitable) general monomial sets (see Theorem 1.4).

1.3.

A generalized flat extension theorem. We need some definitions to state our extension of Theorem 1.2. For C ⊆ M n ,

C + := C ∪ n i=1 x i C = {m, x 1 m, . . . , x n m | m ∈ C} and ∂C := C + \ C
are called, respectively, the closure and the border of C. The set C ⊆ M n is said to be connected to 1 if 1 ∈ C and every monomial m ∈ C \ {1} can be written as

m = x i1 • • • x i k with x i1 , x i1 x i2 , . . . , x i1 • • • x i k ∈ C. For instance, C is connected to 1 if C is closed under taking divisions. For example, {1, x 2 , x 1 x 2 } is connected to 1 but {1, x 1 x 2 } is not. We now state our main result. Theorem 1.4. Consider a sequence y = (y a ) a∈C + •C + , where C ⊆ M n is finite and connected to 1. If M C + (y) is a flat extension of M C (y), then there exists a (unique) sequence ỹ = (ỹ) a∈Mn for which M (ỹ) is a flat extension of M C + (y).
The proof is delayed till Section 2. Note that Theorem 1.2 follows directly from Theorem 1.4 applied to the case C = M n,t-1 . Thus our result can be seen as a sparse version of Theorem 1.2, which applies to a more general monomial set C, not necessarily the full set of monomials up to a given degree. We now give an example showing that the assumption that C is connected to 1 cannot be omitted.

Example. For n = 1, consider the set C = {1, x 3 }, which is not connected to 1, with ∂C = {x, x 4 }. Consider the sequence y ∈ R C + •C + defined by y 1 = y x = y x 2 = 1, y x 3 = y x 4 = y x 5 = a and y x 6 = y x 7 = y x 8 = b, where a, b are scalars with b = a 2 . Then, rank M C + (y) = rank M C (y) = 2. If there is a flat extension M (ỹ) of M C + (y),
then its principal submatrix indexed by C + ∪ {x 2 } has the form:

M C + ∪{x 2 } (ỹ) =       1 x 3 x x 4 x 2 1 1 a 1 a 1 x 3 a b a b a x 1 a 1 a a x 4 a b a b b x 2 1 a a b a       However, 1 -x ∈ ker M C + (y) implies x -x 2 ∈ ker M C + ∪{x 2 } (ỹ) (see (2.
2)) and thus 1 = a = b, contradicting our choice b = a 2 . Hence no flat extension exists.

1.4. Basis-free reformulation. Here we reformulate our result in a basis-free setting. Moment matrices correspond indeed to choosing the monomial basis M n in the polynomial ring K[x] and its dual basis D n in the dual space K[x] * . Given Λ ∈ K[x] * , the operator

H Λ : K[x] → K[x] * p → p • Λ
is known as a Hankel operator. Its matrix with respect to the bases M n and D n is precisely the moment matrix (Λ(x α+β )) α,β∈Mn = M (y) of the sequence y = (Λ(a)) a∈Mn . The kernel of H Λ , ker

H Λ = {p ∈ K[x] | Λ(pq) = 0 ∀q ∈ K[x]}, is an ideal in K[x]. Moreover, when K = R
H C + Λ : Span(C + ) → Span(C + ) * p → p • Λ
and its restriction to Span(C) is H C Λ : Span(C) → Span(C) * . We have the following mappings:

(1.1) Span(C) ker H C Λ σ1 ←- Span(C) ker H C + Λ ∩ Span(C) σ2 -→ Span(C + ) ker H C + Λ
where σ 1 is onto and σ 2 is one-to-one, so that

(1.2) dim Span(C) ker H C Λ ≤ dim Span(C) ker H C + Λ ∩ Span(C) ≤ dim Span(C + ) ker H C + Λ .
Thus, rank Λ . 1.5. Border bases and commuting multiplication operators. We recall here a result of [START_REF] Mourrain | A new criterion for normal form algorithms[END_REF] about border bases of polynomial ideals that we exploit to prove our flat extension theorem. Let B := {b 1 , . . . , b N } be a finite set of monomials. Assume that, for each border monomial x i b j ∈ ∂B, we are given a polynomial of the form

H C + Λ = rank H C Λ (
g (ij) := x i b j - N h=1 a (ij) h b h where a (ij) h ∈ K. The set (1.3) F := {g (ij) | i = 1, . . . , n, j = 1, . . . , N with x i b j ∈ ∂B}
is known as a border prebasis [START_REF] Kehrein | An algebraist's view on border bases[END_REF] or a rewriting family for B [START_REF] Mourrain | A new criterion for normal form algorithms[END_REF]. When the set B contains the constant monomial 1, one can easily verify that B is a generating set for the quotient space K[x]/(F ), where (F ) is the ideal generated by the set F . When B is connected to 1, Theorem 1.6 below characterizes the case when B is a basis of K[x]/(F ), in which case F is said to be a border basis of the ideal (F ). For this, for each i = 1, . . . , n, consider the linear operator:

(1.4)

χ i : Span(B) → Span(B) b j → χ i (b j ) = x i b j if x i b j ∈ B, N h=1 a (ij) h b h if x i b j ∈ ∂B extended to
Span(B) by linearity. When B is a basis of K[x]/(F ), χ i corresponds to the "multiplication operator by x i " from K[x]/(F ) to K[x]/(F ) and thus the operators χ 1 , . . . , χ n commute pairwise. The next result of [START_REF] Mourrain | A new criterion for normal form algorithms[END_REF] shows that the converse implication holds when B is connected to 1; this was also proved later in [START_REF] Kehrein | An algebraist's view on border bases[END_REF] when B is closed under taking divisions.

Theorem 1.6. [START_REF] Mourrain | A new criterion for normal form algorithms[END_REF] Let B ⊆ M n be a finite set of monomials which is connected to 1, let F be a rewriting family for B as in (1.3), and let χ 1 , . . . , χ n be defined as in (1.4). The set B is a basis of the quotient space K[x]/(F ) if and only if the operators χ 1 , . . . , χ n commute pairwise.

The proof of our sparse flat extansion theorem is an adaptation of this result to kernels of Hankel operators, where we omit the assumption that B is connected to 1.

1.6. Contents of the paper. Section 2 contains the proof of our generalized flat extension theorem and we mention some applications in Section 3. In particular, we observe that Theorem 1.2 is an 'easy' instance of our flat extension theorem (since one can prove existence of a basis connected to 1). We also point out the relevance of the flat extension theorem to polynomial optimization and to the problem of computing real roots to systems of polynomial equations.

Proof of the flat extension theorem

We give here the proof of Theorem 1.5 (equivalently, of Theorem 1.4). We will often use the following simple observations, which follow directly from the assumption that rank

H C + Λ = rank H C Λ : For all p ∈ Span(C + ), (2.1) p ∈ ker H C + Λ def. ⇐⇒ Λ(ap) = 0 ∀a ∈ C + ⇐⇒ Λ(ap) = 0 ∀a ∈ C, (2.2) p ∈ ker H C + Λ and x i p ∈ Span(C + ) =⇒ x i p ∈ ker H C + Λ . Our objective is to construct a linear form Λ ∈ K[x] * whose Hankel operator H Λ is a flat extension of H C + Λ . Let B ⊆ C for which rank H C + Λ = rank H B Λ = |B|.
Note that we can assume that 1 ∈ B. Indeed, if no such B exists containing 1, then Λ(p) = 0 ∀p ∈ Span(C + ) and one can easily verify that this implies that Λ is identically zero, in which case the theorem trivially holds.

From the assumption: rank

H C + Λ = rank H B Λ = |B|,
χ i in (1.4) maps p ∈ Span(B) to χ i (p) = π(x i p) ∈ Span(B). We show that χ 1 , . . . , χ n commute pairwise. Set K := ker H C + Λ . Lemma 2.1. χ i • χ j = χ j • χ i . Proof. Let m ∈ B. Write π(x i m) := b∈B λ i b b (λ i b ∈ R).
We have:

χ j • χ i (m) = χ j ( b∈B λ i b b) = b∈B λ i b χ j (b) = b∈B λ i b (x j b -f (x j b)) = x j ( b∈B λ i b b) -b∈B λ i b f (x j b) = x j (x i m -f (x i m)) -b∈B λ i b f (x j b).
Therefore,

p := χ j • χ i (m) -χ i • χ j (m) = x i f (x j m) -x j f (x i m) p1 + b∈B λ j b f (x j b) -λ i b f (x i b) p2 .
We show that p 1 ∈ K. Indeed, ∀a ∈ C, Λ(ap 1 ) = Λ(ax i f (x j m) -ax j (x i m)) = 0 since ax i , ax j ∈ C + and f (x i m), f (x j m) ∈ K; by (2.1), this shows that p 1 ∈ K. As p 2 ∈ K too, this implies p ∈ K and thus p = 0, because p ∈ Span(B).

Our objective now is to show that B is a basis of K[x]/(F ) and that, if π denotes the projection from K[x] onto Span(B) along (F ), then the operator Λ defined by Λ(p) = Λ(π(p)) for p ∈ K[x], defines the desired flat extension of Λ. Note that when B is connected to 1, Theorem 1.6 implies directly that B is a basis of K[x]/(F ). As we do not assume B connected to 1, we cannot apply Theorem 1.6, but our arguments below are inspired from its proof. In particular, we construct the projection π via the mapping ϕ from (2.4) below.

As the χ i 's commute, the operator f (χ

) := f (χ 1 , . . . , χ n ) is well defined for any polynomial f ∈ K[x]. Then K[x] acts on Span(B) by (f, p) ∈ K[x] × Span(B) → f (χ)(p) ∈ Span(B). Recall that 1 ∈ B. The mapping (2.4) ϕ : K[x] → Span(B) f → f (χ) (1)
is a homomorphism and, by the following property, (

) = f (χ)(g(χ)(1)) = f (χ)(ϕ(g)) ∀f, g ∈ K[x], 2.5) ϕ(f g
ker ϕ is an ideal in K[x]. We now prove that ϕ coincide on Span(C + ) with the projection π on Span(B) along

K = ker H C + Λ . Lemma 2.2. For any element m ∈ C + , ϕ(m) = π(m).
Proof. We use induction on the degree of m.

If m = 1, we have ϕ(1) = π(1) = 1 since 1 ∈ B. Let m = 1 ∈ C + . As C is connected to 1, m is of the form m = x i m 1
for some m 1 ∈ C + . By the induction assumption, we have ϕ(m 1 ) = π(m 1 ). Then,

ϕ(m) = ϕ(x i m 1 ) = χ i (ϕ(m 1 )) = χ i (π(m 1 )) = x i π(m 1 ) -κ, with κ ∈ F ⊆ K. But we also have m = x i m 1 = x i (π(m 1 ) + m 1 -π(m 1 )) = x i π(m 1 ) + x i κ 1 where κ 1 = m 1 -π(m 1 ) ∈ K. We deduce that m = ϕ(m) + κ + x i κ 1 = ϕ(m) + κ 2 with κ 2 = κ + x i κ 1 ∈ K + ∩ Span(C + ). As κ 1 ∈ K and x i κ 1 ∈ Span(C + ), we deduce using (2.1) that x i κ 1 ∈ K, thus implying κ 2 ∈ K. As ϕ(m) ∈ Span(B), it coincides
with the projection of m on Span(B) along K. This implies directly:

(2.6) ϕ(b) = b, ϕ(x i b) = χ i (b) ∀b ∈ B ∀i = 1, . . . , n, (2.7)
Λ(pq) = Λ(p ϕ(q)) = Λ(ϕ(p)ϕ(q)) ∀p, q ∈ Span(C + ). Λ in the canonical bases. Consider a total degree monomial ordering of C and let B ⊆ C index a maximum linearly independent set of columns of M which is constructed by the greedy algorithm using the ordering . One can easily verify that B is closed under taking divisions (cf. [START_REF] Lasserre | A prolongation-projection algorithm for computing the finite real variety of an ideal[END_REF]).

The following example shows that, even if C is connected to 1, there may not always exist a base B connected to 1 for H C Λ (which justifies our generalisation of Theorem 1.6 to kernels of Hankel operators). 3.2. Application to polynomial optimization. We point out here the relevance of the flat extension theorems to polynomial optimization and to the problem of computing the real roots to polynomial equations. In this section, we take again K = R.

The truncated moment problem has recently attracted a lot of attention also within the optimization community, since it can be used to formulate semidefinite programming relaxations to polynomial optimization problems (see [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF]). Moreover the flat extension theorem of Curto and Fialkow permits to detect optimality of the relaxations and to extract global optimizers to the original optimization problem (see [START_REF] Henrion | Detecting global optimality and extracting solutions in Glop-tiPoly[END_REF]). Here is a brief sketch; see e.g. [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF] and references therein for details.

Suppose we want to compute the infimum p * of a polynomial p over a semialgebraic set K defined by the polynomial inequalities g 1 ≥ 0, . . . , g m ≥ 0. For any integer t ≥ deg(p)/2 and such that t ≥ d j := ⌈deg(g j )/2⌉, consider the program:

(3.1) p * t := inf Λ(p) s.t. Λ ∈ (R[x] 2t ) * , Λ(1) = 1, Λ 0, g j • Λ 0 (∀j ≤ m).
Here, Λ 0 means that Λ is positive (i.e., Λ(p 2 ) ≥ 0 for all p ∈ R[x] t ) and the localizing conditions g j • Λ 0 (i.e. Λ(g j p 2 ) ≥ 0 for all p ∈ R[x] t-dj ) aim to restrict the search for a representing measure suported by the set K (cf. [START_REF] Curto | The truncated complex K-moment problem[END_REF][START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF]). Using moment matrices, the program (3.1) can be formulated as an instance of semidefinite programming for which efficient algorithms exist (see e.g. [START_REF] Vandenberghe | Semidefinite Programming[END_REF][START_REF]Handbook of Semidefinite Programming[END_REF]). We have:

p * t ≤ p * , with equality if H Mn,t Λ is a flat extension of H M n,t-d Λ
for an optimum solution Λ to (3.1) (d := max j d j ). In that case, the atoms of the representing measure (which exists by Corollary 1.3) are global minimizers of p over the semialgebraic set K and they can be computed from Λ [START_REF] Henrion | Detecting global optimality and extracting solutions in Glop-tiPoly[END_REF]. Moreover, they are all the global minimizers when H Mn,t Λ has the maximum possible rank among all optimum solutions to the semidefinite program (3.1).

As shown in [START_REF] Lasserre | Semidefinite characterization and computation of zero-dimensional real radical ideals[END_REF], the truncated moment problem also yields an algorithmic approach to the problem of computing the real roots to polynomial equations g 1 = 0, . . . , g m = 0 (assuming their number is finite). Indeed, this amounts to finding all global minimizers to a constant polynomial, say p = 0, over the real variety K := {x ∈ R n | g j (x) = 0 ∀j = 1, . . . , m}. Consider the semidefinite program (3.1) where the localizing conditions now read g j • Λ = 0 ∀j. For t large enough, the program (3.1) has a maximum rank solution which is a flat extension and thus, as noted above, all points of K can be computed from this solution. See [START_REF] Lasserre | Semidefinite characterization and computation of zero-dimensional real radical ideals[END_REF] for details.

A concern in this type of approach is the size of the matrices appearing in the semidefinite program (3.1). In order to improve the practical applicability of this approach, it is crucial to derive semidefinite programs involving matrices of moderate sizes. For this one may want to consider moment matrices indexed by sparse sets of monomials instead of the full degree levels M n,t . This is where our new sparse flat extension theorem may become very useful. It will be used, in particular, in [START_REF] Lasserre | Moment matrices, border bases and real radical ideals[END_REF].

The approach in [START_REF] Lasserre | Semidefinite characterization and computation of zero-dimensional real radical ideals[END_REF] also permits to find the real radical of the ideal generated by the polynomials g 1 , . . . , g m . Indeed, if Λ ∈ (R[x]) * is positive, then the kernel of its Hankel operator H Λ is a real radical ideal [START_REF] Laurent | Revisiting two theorems of Curto and Fialkow on moment matrices[END_REF] and, under the conditions of Theorem 3.2, ker H C + Λ generates a real radical ideal. These facts explain the relevance of moment matrices and Hankel operators to the problem of finding the real radical of a polynomial ideal. For instance, this permits to weaken the assumptions in Proposition 4.1 of [START_REF] Lasserre | Semidefinite characterization and computation of zero-dimensional real radical ideals[END_REF] and to strengthen its conclusions; more precisely, we do not need to assume the commutativity of the operators χ i 's (as this holds automatically, by Lemma 2.1) and we can claim that the returned ideal is real radical (by the above argument).

  its entries are given by a sequence y = (y c ) c∈C•C , where C • C := {ab | a, b ∈ C}, and we can write M = M C (y).

  we have the direct sum decomposition: Span(C + ) = Span(B) ⊕ ker H C + Λ , and thus (2.3) ∀p ∈ Span(C + ) ∃! π(p) ∈ Span(B) such that f (p) := p -π(p) ∈ ker H C + Λ . Then the set F := {f (m) = m -π(m) | m ∈ ∂B} is a rewriting family for B and, for i = 1, . . . , n, the linear operator

Proposition 3 . 1 .

 31 Let Λ ∈ (Span(C + • C + )) * , where C := M n,t-1 . If rank H C + Λ = rank H C Λ ,then there exists B ⊆ C closed under taking divisions (and thus connected to 1) for which rank H C + Λ = rank H B Λ = |B|. Proof. Let M = (Λ(ab)) a,b∈C + denote the matrix of H C +

  and rank H C Λ = rank H C + Λ = 2. As 1 -x 1 ∈ ker H C + Λ , the only sets indexing a column base for H C Λ are B = {1, x 1 x 2 } and {x 1 , x 1 x 2 }, thus not connected to 1. Combining Theorem 1.5 with Theorem 1.1 we obtain the following extension of Corollary 1.3. Theorem 3.2. Let Λ ∈ (Span(C + • C + )) * , where C ⊆ M n is finite and connected to 1. Assume that Λ is positive and that rank H C + Λ = rank H C Λ . Then the sequence y = (Λ(a)) a∈C + •C + has a representing measure.

  and Λ is positive, i.e. when Λ(p 2 ) ≥ 0 for all p ∈ R[x], ker H Λ is a real radical ideal[START_REF] Laurent | Revisiting two theorems of Curto and Fialkow on moment matrices[END_REF]. Theorem 1.1 means that Λ ∈ R[x] * is positive with rank H Λ < ∞ if and only if there exists a nonnegative finite atomic measure µ for which Λ(p) = p(x)µ(dx) for all p ∈ R[x].Truncated Hankel operators can be analogously defined. Given C ⊆ M n and Λ ∈ (Span(C + • C + )) * , the corresponding Hankel operator is

  in which case we also say that H C + Λ is a flat extension of H C Λ ) if and only if equality holds throughout in (1.2), i.e. both σ 1 and σ 2 in (1.1) are isomorphisms or, equivalently, if Span(C + ) = Span(C) + kerH C + Theorem 1.5. Let Λ ∈ (Span(C + • C + )) *, where C ⊆ M n is finite and connected to 1, and assume that rank H C +

Λ

and ker

H C Λ = ker H C + Λ ∩ Span(C

). Theorem 1.4 can be reformulated as follows. Λ = rank H C Λ . Then there exists (a unique) Λ ∈ R[x] * for which H Λ is a flat extension of H C + Λ , i.e. Λ coincides with Λ on Span(C + • C + ) and rank H Λ = rank H C +

Lemma 2.3. For all p, q ∈ Span(C + ), Λ(pq) = Λ(ϕ(pq)).

Proof. We first show by induction on the degree of m ∈ C + that (2.8) Λ(mb) = Λ(ϕ(mb)) ∀b ∈ B.

The result is obvious if m = 1. Else, as C + is connected to 1, we can write m = x i m 1 where m 1 ∈ C + . Using first (2.7) and then (2.6), we find:

Next, using first the induction assumption and then (2.5), (2.6), we find:

thus showing (2.8). We can now conclude the proof of the lemma. Let p, q ∈ Span(C + ). Then, using successively (2.7), (2.8), (2.5), (2.6), Λ(pq) is equal to

We can now conclude the proof of Theorem 1.5. Let Λ be the linear operator on

We show that H Λ is the unique flat extension of

As F is a rewritting family for B and B contains 1, B is a generating set of K[x]/(F ) and thus dim K

Λ , and we have the direct sum:

. This shows the unicity of the flat extension of H C + Λ , which concludes the proof of Theorem 1.5.

Applications

3.1. Application to the flat extension theorem of Curto and Fialkow. Theorem 1.2 is in some sense an 'easy' instance of Theorem 1.4. Indeed, under its assumptions, one can show existence of a maximum rank principal submatrix of M t-1 (y) indexed by a monomial set B connected to 1 which, as noted in the proof of Theorem 1.4, permits to apply Theorem 1.6.