Math Overflow Recent Questions

Subscribe to Math Overflow Recent Questions feed
most recent 30 from 2018-06-24T03:46:36Z

Constructive proof of existence of non-separable normed space

Fri, 03/09/2018 - 05:48

I am looking for a constructive proof of one of the following two statements. If they are not constructively provable, I would be very thankful for an explanation as to why that is so (i.e., at which point in a proof must non-constructive means be employed?).

  1. There exists a normed space X such that for all Y $\subset$ X, if Y is denumerable, then Y is not dense in X.

  2. There exists a normed space X such that for all Y $\subset$ X, if Y is dense in X, then Y is not denumerable.

I'd consider a proof constructive if it includes no applications of the:

  • Law of Excluded Middle: $\phi$ $\lor$ $\neg$$\phi$
  • Law of Double Negation Elimination: $\neg$$\neg$$\phi$ $\rightarrow$ $\phi$
  • Axiom of Choice or any of its equivalents (Zorn's Lemma, etc.).

Suggestions would be much appreciated.

partially commutative monoid

Thu, 03/08/2018 - 10:55

Let $G$ be a simple graph with vertex $I$ and edge set $E$. I am defining $M(G)$ to be the quotient of the free monoid $I^*$ on $I$ by the relations $ab=ba$ and $c^2 = 1$ whenever $\{a,b\} \notin E(G)$ and $c \in I$ is arbitrary.

I have the following questions about the monoid $M(G)$.

  1. Is this monoid $M(G)$ well studied in the literature?

  2. What are some algebraic combinatorics or general combinatorial significance of this monoid?

Thanks for your time and have a good day.

Spectrum of orthogonality graph (2)

Thu, 03/08/2018 - 03:05

The orthogonality graph, $\Omega(n)$, has vertex set the set of $\pm 1$ vectors of length $n$, with orthogonal vectors being adjacent.

I am only interested when $4|n$, since otherwise $\Omega(n)$ is empty or bipartite. I am keen to know the spectrum of $\Omega(n)$ - the eigenvalues and their multiplicities. In particular I am seeking the inertia of $\Omega(n)$ - that is the numbers of positive, zero and negative eigenvalues. Many thanks Clive

Number of zeroes of derivatives of the polynomial

Wed, 03/07/2018 - 04:15

What are the maximal number of zeroes the polynomial of degree d and all of its derivatives can have at $k$ points? Say polynomial is over $\mathbb(C)$. I am interested in this question for a constant $k$, say 3. If $k\rightarrow \infty$ clearly polynomial can have $d$ zeroes and and its $i$'th derivative can have $d-i$ zeroes. The problem is that ussually polynomial and its derivatives have different zeroes.

Does there exist an example of the polynomial with more than k+d zeroes for him and its derivatives?

Relationship between decay constant (T) and Rt60

Wed, 03/07/2018 - 04:09

In acoustics, concerning the decay of energy in a sound field or of a resonance in, for example, a musical instument or a loudspeaker, two time periods are related; the 'relaxation time' for the signal to decay to 36% (e-1) of intitial value, and Rt60, deemed the point at which the energy has, for all practical purposed, diminished to zero.

One confusion is that acoustic energy is difficult to measure, so sound pressure is used as this is easy to measure, with time and frequency. Hence, the theoretical approach is based on energy dissipating to one millionth of original, where as working in sound pressure (analogous to volts), it is a diminution to one thousandth of original pressure level.

I find in published literature two seemingly inconsistent terms:

T (secs) (diminution to 36%) x 6.9 = Rt60 (secs) and T (secs) (diminution to 36%) x 13.8 = Rt60 (secs)

Only one can be correct.

Note that 6.9 is half of 13.8

I suspect that this is somehow related to the power/amplitude 10log or 20log element, but despite days on this, I'm just not bright enough to work it out!

Your thoughts would be most appreciated.


Source 1:

Source 2:

Many thanks!

On minimum of a function?

Wed, 03/07/2018 - 03:49

Given $A,B\in\Bbb R^{n\times n}$ is there a technique find $\min_{ T\in O(n,\Bbb R)}\|A-TBT^{-1}\|_2$?

Do maximally almost periodic groups embed homeomorphically into their Bohr compactifications?

Wed, 03/07/2018 - 03:37

If $G$ is a Hausdorff topological group and $bG$ is its Bohr compactification, Wikipedia says that $G$ is called maximally almost periodic (MAP) if and only if the natural map $i : G \to bG$ is injective. Equivalently, MAP groups are those groups the points of which are separated by the finite-dimensional unitary representations. My question is:

if $G$ is MAP, is $i$ a homeomorphism onto $i(G)$, or is it only injective?

(I would like to know if topological properties and regular measures on $i(G)$ can be pulled back on $G$.)

Integer factorization

Wed, 03/07/2018 - 03:26

Is there a way to find out the first few digits of the factors of the RSA numbers.(RSA-1024 or RSA-2048)

I do not want to get all the digits but only first 4-5 digits.

Existence of equation about the product of the divisor sum function

Wed, 03/07/2018 - 02:55

Let $\sigma_k(n)$ be the sum of the $k$-th powers of the positive divisors of $n$ and $\mu(n)$ be the Möbius function.

As Arithmetic function - Wikipedia mentioned, there is an equation that $$\sigma_k(u) \sigma_k(v) = \sum_{d~| \gcd(u, v)}{d^k \sigma_k\left(\frac{u v}{d^2}\right)}$$ which can also be represented as $$\sigma_k(u v) = \sum_{d~| \gcd(u, v)}{\mu(d) d^k \sigma_k\left(\frac{u}{d}\right) \sigma_k\left(\frac{v}{d}\right)}.$$

I wonder to know if there exists an equation between $\sigma_k(u v w)$ and $\sigma_k(u) \sigma_k(v) \sigma_k(w)$?

The Chow monoid is an algebraic set

Wed, 03/07/2018 - 01:55

Let $X\subset \mathbb{P}^N(\mathbb{C})$ be an irreducible algebraic variety. The ($p$th) Chow monoid of $X$ is given by $$C_p(X)=\bigsqcup_{d\geq 0}C_{p,d}(X),$$ where $C_{p,d}(X)$ are the $p$-cycles having degree $d\geq 0$. It's very well known that every $C_{p,d}(X)$ is a complex algebraic set, but however, I'm not able to find a reference in which this fact is proved. Can you help me?

On the total number of hamiltonian cycle in I-graph [migrated]

Wed, 03/07/2018 - 00:53

prove that the total number of hamiltonian cycle in I-graph where n is odd and j=k is $(2n)^2$

Definition of I-graph

Which continuous function is optimal for sieving?

Tue, 03/06/2018 - 23:25

In 1968, Barban and Vehov considered [1] the problem of determining for which continuous functions $\rho:\mathbb{R}^+\to [0,1]$ satisfying certain properties ($\rho(t)=1$ for $t\leq U_0$, $\rho(t)=0$ for $t>U_1$) the sum $$S(x) = \sum_{n\leq x} \left(\mathop{\sum_{d|n}}_{d\leq U_0} \rho(d) \mu(d) \right)^2$$ was minimal. (Assume from now on that $x>U_1>U_0$. They showed that the choice $\rho(t) = \rho_0(t) = \log(t/U_0)/\log(U_1/U_0)$ for $U_0<t\leq U_1$ was grosso modo optimal, in the sense of giving a sum $S(x)$ whose main term is no more than a constant times the minimal value that such a sum $S(x)$ could take. Later, Graham showed that, for $\rho(t) = \rho_0(t)$ as above, $S(x)$ actually asymptotes to $x/\log(U_1/U_0)$.

(a) What is the easiest way to show that this is the least possible leading term in an asymptotic for $S(x)$ for any function $\rho$ satisfying the above conditions? (That the order of magnitude is correct is clear from estimates on rough numbers, but such estimates have Buchstab's function in front.)

(b) What work, if any, has been done to date on the second-order term in the asymptotics? Graham gave a bound of the form $x/\log(U_1/U_0) + O(x/\log^2(U_1/U_0))$. I recently finished showing that, for $\rho$ as above and $U_0\ggg \sqrt{X}$, $S(x)$ asymptotes to $x/\log(U_1/U_0) - c x/\log^2(U_1/U_0)$, where $c$ is an explicit constant that is positive under some broad conditions ($U_1/U_0\geq 8$). I have no idea as to whether $c$ is the best value one could obtain for any $\rho$ satisfying the conditions.

In the range $U_1\lll X$, one could of course compare the corresponding constant $c'$ to the constant coming from Selberg's sieve. At the same time, one could change the conditions slightly (requiring $\rho$ to be the rescaling of a continuous function $\eta$ independent of $U_0$, $U_1$ and $X$, say) so as to exclude Selberg's sieve from consideration -- and then we would only have an upper bound on $c$. Is anything better known?

[1] M. B. BARBAN AND P. P. VEHOV, On an extremal problem, Trudy Moscov. Obsch. 18 (1968), 83-90.

Why c.p.c order zero maps induce morphism between cuntz semigroups

Tue, 03/06/2018 - 22:48

Maybe a naive question:

Right now I am reading the paper ``Completely positive maps of order zero'' written by Wilhelm Winter and Joachim Zacharias. I do not quite understand the last corollary when they proved the induced map between Cuntz semigroups of a c.p.c order zero map between algebras preserves addition. Why we need the map is order zero?

To be simple, suppose that $A, B$ are $C^*$-algebras. Let $a,b\in A_+$ and $\varphi: A\rightarrow B$ be a c.p.c order zero map. They claim that if $a,b\in A$ are orthogonal, then so are $\varphi(a), \varphi(b)\in B$, whence $$\varphi(a\oplus b)=\varphi(a)\oplus \varphi(b)$$.

The first $\varphi$ is interpreted to be the amplification of $\varphi$, i.e. $\varphi\otimes id_{M_2}$ I believe. However, I guess that the equation above hold for every c.p.c map. Because $a\oplus b= a\otimes e_{11}+b\otimes e_{22}$ and $\varphi\otimes id_{M_2}(a\otimes e_{11}+b\otimes e_{22})= \varphi(a)\otimes e_{11}+ \varphi(b)\otimes e_{22}=\varphi(a)\oplus \varphi(b)$.

I believe I must miss something. But I cannot find where I was wrong.

Thank you for all helps!

Do commutative rings with "interesting" Jacobson radicals turn up "in nature"?

Tue, 03/06/2018 - 21:09

Let $R$ be a commutative ring. Let's say that the Jacobson radical $J(R)$ of $R$ is uninteresting if

  1. $J(R)$ coincides with the nilradical, or

  2. $J(R)$ is the intersection of a finite number of maximal ideals.

It seems as if most rings used in algebraic geometry have uninteresting Jacbson radical:

  • Every finitely-generated commutative algebra over a field or over a Dedekind domain is Jacobson, so its Jacobson radical coincides with its nilradical, and so is uninteresting by (1).

  • Every local or semilocal commutative ring has finitely many maximal ideals, and so has uninteresting Jacobson radical by (2).

For a nonuninteresting example, take the localization $R = \mathbb Z[x]_S$ where $S = \{f(x) \in \mathbb Z[x] \mid f(0) = 1\}$. The maximal ideals of $R$ are of the form $(p,x)$ where $p \in \operatorname{Spec} \mathbb Z$. So the Jacobson radical is $(x)$, which is not uninteresting.

But this example seems rather artificial to me; for example I don't know anywhere a ring like this would show up in algebraic geometry.

Showing an alternating integer series is never $0$

Tue, 03/06/2018 - 20:50

The following series arose in some work related to Hilbert Functions of ideals of points

$$\sum_{k = 0}^m (-1)^k {2m+2 \choose k}[2m(m+1)-k(2m+1)]^{2m-1}.$$

Experimentally, this series is always negative for $m > 0$ and decreases incredibly quickly. We only need that this is never $0$. We have tried rational roots, taking first differences, but have been unable to make much progress. Any help or suggestions are appreciated.

What is the difference between exactness and optimality of an algorithm?

Tue, 03/06/2018 - 19:40

I'm studying some papers related to graph partitioning (GP). It is well-known that the GP problem is NP-Complete. Based on my understanding, it means that there is no polynomial time solution to solve this problem, or there is no optimal solution for that. The following paper mentioned this fact in its introduction: "An exact algorithm for graph partitioning" However, they provided an exact solution for GP using branch-and-bound algorithm. Isn't it a paradox?, I mean I assume that if a problem is NP-Complete, there is also no exact solution for that, right?

Almost-disjoint sequence of sets at singular cardinals and stationary reflection

Tue, 03/06/2018 - 18:04

Let $\mu$ be a singular cardinal of countable cofinality. Let $ADS_\mu$ be the assertion that there exists $\langle A_\alpha\subset \mu: \alpha<\mu^+\rangle$ such that for all $\beta<\mu^+$, there exists $F: \beta \to \mu$ such that $\langle A_\alpha\backslash F(\alpha): \alpha<\beta\rangle$ is pairwise disjoint. It is a well-known fact that $ADS_\mu$ implies the failure of $Refl^*([\mu^+]^{\omega})$, which says for any stationary subset $S$ of $[\mu^+]^\omega$, there exists $W\in [\mu^+]^{\aleph_1}$ with $\omega_1\subset W$ and $cf(\sup W)=\omega_1$ such that $S\cap [W]^{\omega}$ is stationary.

$Refl([\mu]^{\omega})$ is almost the same assertion as $Refl^*([\mu^+]^\omega)$ except we do not require $cf(\sup W)=\omega_1$ (so it's weaker). It is also known that these two principles in general are not equivalent.

My question is: does $ADS_\mu$ imply the failure of $Refl([\mu^+]^\omega)$?

Where do models of false theories exist?

Tue, 03/06/2018 - 17:53

I have some difficulties in understanding the [uni]verse platonic view. How are we to understand the existence of a model of a false theory? what is the relationship of this model to the platonic world of sets?

My personal try is the following, let's assume the existence of a platonic universe $P^{sets}$ of sets, and also another universe $P^\in$ that serves as a relational universe, i.e., that can stand as a representative of the relation epsilon $\in$ in the real world. For example $P^\in$ might be a universe of some object representation of "ordered pairs" of sets, these ordered pairs are primitive ones, they stand for really existing objects exemplifying ordered pairs in a platonic realm. So $P^\in$ would be a really existing platonic membership relation between objects of $P^{sets}$.

Now when we say for example the rules of $ZFC$ are true, in a platonic sense, would that be taken to mean that the sets in $P^{sets}$ would be related to each other by the platonic membership relation in a manner that abides $ZFC$ rules.

So now when we say that $ZFC$ can interpret $ZF\neg C$ then this mean that the later is consistent (should $ZFC$ be consistent) so there would exist a model of $ZF\neg C$, but how I'm to understand the existence of this model in the platonic world? is it the case that the interpretation would be a pair of subsets of $P^{sets}$ one representing a domain and the other is a set of set-ordered pairs (non primitive ones, i.e. interpreted ordered pairs as special kinds of sets), and so the rerlation object interpreting the membership relation is not a real relational one, i.e. not composed of primitive membership ordered pairs??? as it is the case with ZFC? so this model is deemed as not real?

Is that a good analogy? I mean I want to conceal two matters: that there EXISTs a model of a false but consistent theory, if we are to hold platonistic views, then this existence must be in some reality? otherwise the assertion "there exists" wold have no meaning, now this reality must be taking part in the true platonic world of sets? where else it would be? On the other hand we must differentiate this kind of existence of a model of a false theory from the existence of a model of a true theory! that's why I used the "primitive ordered pairs" to represent the relations in the theory, a true theory would have its relation sets being real in the platonic sense, i.e. composed of primitive ordered pairs abiding the rules of that theory, while a false one would not have them real, i.e. the relation on its domain is not composed of primitive ordered pairs.

I always had the following impression:

for every effectively generated theory $T$ we have: $$ Con(T) \to \exists T^* (True(T^*) \wedge T^* inteprets T)$$

the idea can be seen in the above anaology, if a set theory $T$ is consistent but false, still the model of $T$ must be a part of $P^{sets}$ and so there must be a true theory $T^*$ (i.e. $T^*$ satisfied in $P^{sets}$) that can itnerpret $T$, otherwise how can we explain that a model of $T$ must exist? exist where?

Is that impression correct?

I visualize the whole platonic world of mathematics $P^{math}$ as the union of the platonic worlds of the individual disciplines i.e. the union of $P^{arith}$ , $P^{Geom}$ , etc..., I think standard models of those disciplines are the real ones represented by the Platonic realms of those disciplines, i.e. they have real relation sets, as opposed to the fake or false theories which don't have real grounded relations in the platonic world.

I know that this question is in some sense philosophical, but "platonism" especially the [uni]-versed one, is an almost ongoing working assumption of most innovative work in mathematics and set theory, so it is important to at least shed some light on that aspect.

Homomorphic Images of C^*-Algebras

Tue, 03/06/2018 - 17:42

If A and B are C^*-algebras that are algebraically isomorphic to each other, does this imply that they are *-isomorphic to each other?

Naturality of Moore-Postnikov systems

Tue, 03/06/2018 - 14:16

Where in the literature can I find a naturality statement for Moore-Postnikov towers of maps? Something like the following:

Let $f:X\to A$ and $g:Y\to B$ be maps of connected CW-complexes which both admit a Moore-Postnikov tower of principal fibrations. Then a commuting diagram $\require{AMScd}$ \begin{CD} X @>f>> A\\ @V \Phi V V @VV \phi V\\ Y @>>g> B \end{CD} (possibly with some extra conditions) induces maps $\Phi_n:X_n\to Y_n$ between the $n$-th stages of the towers of $f$ and $g$, for all $n\ge1$.