1
$\begingroup$

Definition. A subset $S$ of $\mathbb{R}^n$ is called semi-algebraic if $S$ is a finite Boolean combination of sets of the form $\{ x \in \mathbb{R}^n \mid p(x) \ge 0\}$, where $p \in \mathbb{R}[x]$.

View $\mathbb{C}^n$ as a real $2n$-dimensional vector space and let $\mathsf{T}: \mathbb{C}^n \longrightarrow \mathbb{R}^{2n}$ be the bijective linear transformation such that $$ z \in \mathbb{C}^n \stackrel{\mathsf{T}}{\longmapsto} \begin{bmatrix} \Re z_1 \\ \Im z_1 \\ \vdots \\ \Re z_n \\ \Im z_n \end{bmatrix} \in \mathbb{R}^{2n}. $$

As suggested in a comment here, call $S \subseteq \mathbb{C}^n$ complex semi-algebraic or semi-algebraic in $\mathbb{C}^n$ if $\mathsf{T}(S)$ is semi-algebraic in $\mathbb{R}^{2n}$.

Question. Is there an equivalent definition that involves, perhaps, a set of inequalities involving the modulus?

As an example, if $S := \{z \in \mathbb{C} \mid 1 - \vert z^2 \vert \ge 0\}$, then $\mathsf{T}(S) = \{ x \in \mathbb{R}^2 \mid 1 - (x^2 + y^2) \ge 0 \}$ is semi-algebraic in $\mathbb{R}^2$.

Edit: I've decided to add some context given that someone decided to downvote this post.

The nonnegative inverse eigenvalue problem (NIEP) is to characterize the spectra of (entrywise) nonnegative matrices. The NIEP is unsolved for matrices of order greater than four.

Let $x \in \mathbb{C}^n$. Say $x$ is realizable if the multiset $\Lambda(x) := \{x_1,\dots,x_n\}$ is the spectrum of a nonnegative matrix of order $n$. Let $\mathbb{L}^n := \{ x \in \mathbb{C}^n \mid \Lambda(x) = \sigma(A),~A \in \mathsf{M}_n(\mathbb{R}),~A \ge 0 \}$. (There are some well-known necessary conditions on this set, but we do not mention them here.)

In reviewing the NIEP, Bharali and Holtz [MR2399570] state

Finally, it follows from the Tarski–Seidenberg theorem [38, 29] that all realizable $n$-tuples form a semialgebraic set (see also [16]); i.e., for any given $n$, there exist only finitely many polynomial inequalities that are necessary and sufficient for an $n$-tuple $\Lambda$ to be realizable [emphasis added] as the spectrum of some nonnegative matrix $A$ (this observation was communicated to us by Friedland).

As illustrated above, this is clearly not the case and demonstrates the need for defining a complex semi-algebraic set beyond what I proffered above. Furthermore, a rigorous, "local" definition would give us a certificate of what it means to solve the NIEP.

$\endgroup$
25
  • $\begingroup$ Could you be more precise (than "involving the modulus") on what you allow and what you don't allow to define subsets? $\endgroup$
    – YCor
    Commented Aug 7, 2019 at 20:55
  • 2
    $\begingroup$ That's not the usual definition of semialgebraic set. Usually they are taken to be a finite union of sets $P_i$ which are each defined by one or more polynomial equalities and inequalities. Are you restricting to semialgebraic sets of a special form? $\endgroup$ Commented Aug 8, 2019 at 2:18
  • 1
    $\begingroup$ Are you allowing equations, e.g. $|z|-z=0$, too? Anyway, I have trouble trying to describe the positive ortant in $\mathbb{C}$ using the norm. $\endgroup$ Commented Aug 8, 2019 at 6:31
  • 1
    $\begingroup$ Are you asking if every complex semialgebraic set is the preimage of a real semialgebraic set via the map $z\mapsto(|z_1|,\dots,|z_n|)$? $\endgroup$
    – Ben McKay
    Commented Aug 8, 2019 at 9:19
  • 1
    $\begingroup$ What's wrong with inequalities in $\Re x_k, \Im x_k$ ? They do describe the $x_k$'s. And showing that the solutions to NIEP form a semialgebraic set is easy, one needs to recall that a projection of a semialgebraic set is semialgebraic. $\endgroup$ Commented Aug 9, 2019 at 21:14

2 Answers 2

1
$\begingroup$

Here I unroll the argument in [MR2399570] showing that $\mathbb{L}^n=\mathbf{T}^{-1}(S)$ for a semialgebraic set $S$, to show that at worst [loc.cit.] is a bit too brief, but no more that that.

Given an entrywise nonnegative $n\times n$ matrix $A$, its $n$-tuple of eigenvalues is specified by the polynomial identity $$ \det(\lambda I -A)=\prod_k (\lambda -\lambda_k).\tag{1}$$ On the other hand $$ \det(\lambda I -A)=\sum_{k=0}^n a_k(A)\lambda^k, \qquad \prod_k (\lambda -\lambda_k)=\sum_{k=0}^n \sigma_k(\Lambda)\lambda^k,$$ where $a_k$ are polynomials in the entries of $A$, and $\sigma_k$ are (symmetric) polynomials in $\lambda_j$'s. Thus we can eliminate $\lambda$ from (1), so that it becomes $$ a_k(A)=\sigma_k(\Lambda),\qquad 0\leq k\leq n.\tag{2}$$ Writing $\lambda_k=\mu_k+\sqrt{-1}\nu_k$, $\mu=(\mu_1,\dots,\mu_n)$, $\nu=(\nu_1,\dots,\nu_n)$,
$\sigma_k(\Lambda)=\alpha(\mu,\nu)+\sqrt{-1}\beta(\mu,\nu)$ for real polynomials $\alpha$, $\beta$, and noting that $a_k(A)$ are real, one re-writes (2) as $$ a_k(A)=\alpha_k(\mu,\nu), \quad 0=\beta_k(\mu,\nu)\qquad 0\leq k\leq n.\tag{3}$$

Thus, $\Lambda\in\mathbb{L}^n$ iff there exists $A\geq 0$ so that (3) holds. We now have a semialgebraic set $$(\exists A)\ [(A\geq 0)\wedge (a_k(A)=\alpha_k(\mu,\nu), \ 0=\beta_k(\mu,\nu)\quad 0\leq k\leq n)],\tag{4}$$ which describes $\mathbb{L}^n$, and from which by Tarski-Seidenberg $A$ may be eliminated, to obtain $S$, a semialgebraic set with variables $\mu$ and $\nu$ only, as claimed.


Edit: most known necessary conditions for $\Lambda\in\mathbb{L}^n$ are naturally viewed in terms of $\mu$ and $\nu$, e.g. nonegativity of $k$-power sums $s_k(\Lambda)=\sum_j \lambda_j^k$ (which is (3) in arxiv.org/pdf/1712.05454.pdf).

Appearence of symmetric polynomials $s_k$ is not a coincidence; indeed the set $S$ admits the action of the symmetric group $S_n$ permuting $\lambda_j$'s, as well as the complex conjugation involution. It would be interesting to know whether it's always possible to use only the polynomials invariant under this group to define $S$.

On the other hand, one might want to break the $S_n$-symmetry by adding the condition $\mu_1\geq \mu_2\geq ...\mu_n$ to (4); as well (4) allows to impose further geometric conditions on $\Lambda$, e.g. it's elements forming a convex $n$-gon, matrix semi-stability (all $\mu_j\leq 0$), etc.

$\endgroup$
9
  • $\begingroup$ What was claimed is that the set is semi-algebraic in the complex variables (which is non-sensical) not the real variables. Again, I fully understand that it is semi-algebraic in the real variables but you continue to not understand my objection. $\endgroup$ Commented Aug 10, 2019 at 19:34
  • $\begingroup$ They never say in [MR2399570] explicitly what variables they use. While your question on whether $|\cdot |$ would suffice to produce the needed inequalites is fine, there is nothing wrong with [MR2399570]. $\endgroup$ Commented Aug 10, 2019 at 21:03
  • $\begingroup$ I respectfully disagree. Their treatment of that topic is slipshod (although somewhat acceptable because they were trying to summarize). The inequalities that are required for the solution of the NIEP are in terms of the complex variables, not the real and imaginary variables, which is why my question is pertinent. $\endgroup$ Commented Aug 10, 2019 at 21:05
  • $\begingroup$ @PietroPaparella in your comment to your question you said "it may be possible that their conclusion is correct, but their argument that leads to the conclusion is not. ". I have trouble matching "I fully understand" with "it may be possible that...", which clearly says you had doubts about their argument. I am glad my answer helped to clarify this. $\endgroup$ Commented Aug 10, 2019 at 21:06
  • $\begingroup$ I don't understand why you don't consider this appoach a solution to NIEP. For a fixed $n$, it's a question of running a finite exact algorithm on the system (4) of polynomial equations and inequalities with integer coefficients to obtain $S$, and thus a description of the $\mathbb{L}^n$. $\endgroup$ Commented Aug 10, 2019 at 21:20
1
$\begingroup$

I will jot down some stray (and easy) thoughts, in an effort to engage the question and see whether some aspects of it can be made more precise.

Going out on a limb, I suppose a baseline assumption is that we start out with a collection of basic sets in $\mathbb{C}^n$ (letting $n$ vary) that are considered "definable", such as graphs of complex polynomial functions in several variables, and inverse images of closed and open intervals of $\mathbb{R}$ (including rays) with respect to the modulus function $\mathbb{C} \to \mathbb{R}$. A key question is what sorts of operations we allow to "close up" this collection, but again, I think from the form of the question that minimally we want to close up under the Boolean operations of finite intersections, finite unions, and complementation. Probably also cartesian products of definable sets should be considered definable. Whether we want to close up under taking direct images along projection maps is not yet known, but that would be a powerful assumption and would probably trivialize the problem. On the other hand, if taking direct images is not allowed as a basic operation, then we have more work to do to make the problem precise.

For example, although it wouldn't follow directly from the minimalistic assumptions above, I would guess the OP would allow the set $\{z \in \mathbb{C}: |z + i| - |z - i| \leq 0\}$ as one of the stockpile of definable sets. Similarly for $\{z \in \mathbb{C}: |z + i| - |z - i| \geq 0\}$, and so then the intersection, which is the real axis, would be allowed in the stockpile. Similarly the imaginary axis would be allowed.

Let's see if we can get projection maps to the real and imaginary axes (and by that point, we would be pretty close to the realm of ordinary semialgebraic sets in $\mathbb{R}^{2n}$, although certain issues of definablity would still need to be sorted out). I suspect that the function $z \mapsto \frac1{2}(|1 + z|^2 - |z|^2 - 1)$ would be considered by OP to be a definable function of the form $\mathbb{C} \to \mathbb{R}$; this of course is $z \mapsto Re(z)$. We aren't quite done, but if we now consider the relation

$$\{(z, t) \in \mathbb{C}^2: Re(z) = Re(t) \wedge |t + i| = |t - i|\}$$

(where $=$ in $\mathbb{R}$ is $\leq \wedge \geq$), then this is the graph of a function $\mathbb{C} \to \mathbb{C}$ that represents projection onto the real axis, and projection onto the imaginary axis is obtained similarly.

I am making this CW as it is not clear whether response this would be considered satisfactory to the OP. But I would like the OP to engage seriously with the whole issue of definability (roughly, which functions, baseline sets, and set-forming operations do we allow) that is at the crux of the question once you dig in. Also, to head off one possibility at the pass (and speaking more in a moderator capacity): neither Dima nor I nor any one of the community members seeking to engage have meant to be "patronizing" in any way toward the OP. Some of the discussion in comments I have found unfortunate (and have had to edit, as a moderator); I hope the tone of this response suggests that some patience and care is needed to resolve the issues that are basic here.

$\endgroup$
3
  • 1
    $\begingroup$ Nice! Also $Re(z) = \frac{1}{4}(|z+1|^2-|z-1|^2)$, and $Im(z) = Re(-iz) = \frac{1}{4}(|-iz+1|^2-|-iz-1|^2) = \frac{1}{4}(|z+i|^2-|z-i|^2)$. @PietroPaparella would it be useful for your work to take inequalities that involve $Re(z)$ and $Im(z)$, and rewrite them by subsituting in those expressions $\frac{1}{4}(|z+1|^2-|z-1|^2)$ and $\frac{1}{4}(|z+i|^2-|z-i|^2)$? Would this help get your requested "a set of inequalities involving the modulus"? (These expressions are far from unique, so other ones might be more useful, depending on what you're trying to do.) $\endgroup$ Commented Aug 12, 2019 at 8:30
  • 1
    $\begingroup$ @ZachTeitler There is one issue that remains to be clarified: whether the modulus function is regarded as a function mapping to $\mathbb{C}$ or to $\mathbb{R}$. This is not a pedantic distinction because it's not clear that OP wants to include the standard inclusion $\mathbb{R} \hookrightarrow \mathbb{C}$ as part of the underlying signature of the theory. I think my main question is whether, in the absence of allowing direct images, composition of definable functions would be admitted as definable. (Allowing only Boolean combinations of definable sets is pretty weak and constraining.) $\endgroup$ Commented Aug 12, 2019 at 11:47
  • $\begingroup$ @ZachTeitler: I was not aware of those identities, but they are quite useful for my purposes. $\endgroup$ Commented Aug 12, 2019 at 19:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .