computer science - Reconstructing an ordering of a multiset from its consecutive submultisets

I have some unpublished notes that I think are relevant to this problem, and I am cherry-picking from them. (See also here for a related question.) Because the notes are unpublished I hope it will not be considered poor form to provide a rather lengthy response.

To save myself trouble while picking the relevant parts from them, I will write $q$ in place of $r$ and $k$ in place of $j$. Also, let $B = q^k$ and let $N$ be the length of a generic cyclic word (or necklace) over a $q$-ary alphabet $mathcal{A}_q$.

As Gerhard suggests, the problem can be recast in terms of necklaces and their subwords of length $k$. We introduce the appellation dimgraph for “directed multigraph”. Let $[w]_k$ denote the generalized order $(k – 1)$ de Bruijn dimgraph of the $q$-ary word $w$: i.e., vertices correspond to the $(k – 1)$-tuples, and directed edges correspond to the $k$-tuples in $w$ in the usual way. If $[w′]_k = [w]_k$, we say that $w$ and $w′$ belong to the same order $k$ de Bruijn homology class. It is easy to see that this really is an equivalence relation, which we denote $sim_k$ (suppressing subscripts when there is no risk of confusion). If the size of an equivalence class is greater than unity, it will be necessary to take into account the additional data associated to $p$, but I will not touch on that (or on the formula to determine the multiplicity of a nontrivial equivalence class, though if anyone wants this please leave a comment and I will try to reply with a PDF) here.

For convenience, assume first that $q = 2$ and define the frequency tuple $alpha = alpha(w)$ as the $B$-tuple of natural numbers indicating the frequency of occurrence in $w$ of the (lexicographically ordered) $k$-tuples over $mathcal{A}_q$. For later convenience we take the frequency tuple to be an integral column vector. For example,

$w = 00011 in mathcal{A}_2^5, k = 3 Rightarrow alpha(w) = (alpha_{000},dots,alpha_{111})^T equiv (alpha_0,dots,alpha_7)^T = (1,1,0,1,1,0,1,0)$.

Notice that we start the index at zero: this will be our default convention for all indices relating to $k$-tuples, and context should generally suffice to determine the indexing scheme for a particular object.

The Eulerian property of generalized de Bruijn graphs means that $alpha$ is completely specified by the $B/2 + 1$ components $alpha_0,alpha_1,dots,alpha_{B/2-1},alpha_{B-1}$: conversely, any such assignment completely specifies the corresponding generalized de Bruijn dimgraph—though notice here that we make no implicit requirement that such a dimgraph must as a matter of course be strongly connected (i.e., correspond to a word). We could make other choices for the “free” components: the essential thing is that the two “loop” components $alpha_0$ and $alpha_{B-1}$ must be free, and any other $B/2 – 1$ components will suffice to complete a specification. The reason for this is basically that the Eulerian property (besides its requirement of strong connectivity) provides $B/2$ independent equations in $B$ unknowns.

More explicitly, for k > 1, write the frequency tuple as a column vector:

$alpha = (alpha_0,alpha_{[0]}^{(k)},alpha_{[1]}^{(k)},alpha_{B-1})^T; quad alpha_{[0]}^{(k)} = (alpha_1,dots,alpha_{B/2-1})^T, quad alpha_{[1]}^{(k)} = (alpha_{B/2},dots,alpha_{B-2})^T$.

Now there is an integral matrix—actually there are many integral matrices—satisfying

$alpha_{[1]}^{(k)} = M_{[0 rightarrow 1]}^{(k)} alpha_{[1]}^{(k)}$.

There is an algorithm for computing these matrices for arbitrary $k$: it is just an exercise in index-juggling, however, so we omit the details. The point is that we can dispense with the unnecessary components of frequency tuples for the binary case, although some care must be taken. Also, it turns out to simplify matters considerably if we omit the words of all zeros and all ones from consideration: we will do so without comment when convenient. More generally, it is convenient to require that none of the components of the frequency tuple are zero (which also implies that none of them equal $N$), but we shall be explicit when making such an assumption.

We can treat some of the components of a frequency tuple in the manner just outlined as functions into the natural numbers. In turn, the matrix-tree and BEST theorems can be jointly recast as a recipe for another function—the BEST function—from this space into the natural numbers that gives the cardinality of the de Bruijn equivalence class.

...

With the binary case in hand, we seek to generalize to $k$-tuples over $mathcal{A}_q$. The approach will be somewhat different here. Define ancestor and descendant matrices by

$M_leftarrow := 1_{1 times q} otimes I_{B/q}, quad M_rightarrow := I_{B/q} otimes 1_{1 times q}$.

Now the indegree/outdegree (I/O) or weak Eulerian property reduces to

$M_leftarrow alpha = M_rightarrow alpha$.

Nothing is lost here by forming the augmented ancestor and descendant matrices

$tilde M_leftarrow := delta_1 otimes M_leftarrow + I_B, quad tilde M_rightarrow := delta_1 otimes M_rightarrow + I_B$

and characterizing the I/O property instead by

$tilde M_leftarrow alpha = tilde M_rightarrow alpha$.

The augmented matrices are invertible, and so we can rewrite the I/O property once more as

$M_{(I/O)}alpha equiv left( tilde M_rightarrow^{-1} tilde M_leftarrow -I right)alpha = 0$.

In other words, a proper frequency tuple must belong to the kernel of the consistency matrix on the LHS above. The dimension $d$ of this in/out (I/O) kernel $ker_{I/O}(q,k)$ is just the number of independent variables required to determine a frequency tuple.

This number is $d = B – B/q + 1$. A sketch of a proof is as follows: of the $B$ edges (including any with multiplicity zero) in an order $(k – 1)$ generalized de Bruijn dimgraph, $q$ are loops: the corresponding frequency tuple components obviously need to be treated as free variables. For the remaining edges, we have B/q independent linear equations in $B – q$ variables. This gives a net of $B – B/q$ independent variables for a minimal integral solution to the linear equations. The +1 is accounted for by scaling.

Accordingly, if the word length is fixed to $N$ then evidently there are $B – B/q$ free components.

For small $q, k$ an exact/integral basis for the in/out kernel can be formed easily (e.g., by using the null command in MATLAB with the r option), and since these are the only cases we can realistically address, we will not bother with an algorithm.

We have two comments at this point. The first is that the reader should be convinced (or take it as an exercise to prove) that the I/O kernel contains an integer lattice whose primitive cells are relatively small (a precise formulation and attendant proof are probably rather technical, and certainly uninteresting). The second is that the lattice can be generated by a positive integral basis: the few negative entries above can clearly be made to go away with a few elementary linear operations.

That is, we consider the I/O lattice

$Lambda_{I/O}(q,k) :- ker_{I/O}(q,k) cap mathbb{Z}^B$

and the associated lattice cone

$Lambda_{I/O}^{0+}(q,k) := ker_{I/O}(q,k) cap mathbb{N}^B$.

Except for some degenerate cases corresponding to disconnected generalized de Bruijn dimgraphs (to be addressed in the sequel), points in this cone correspond to valid frequency tuples. For computational purposes we want to be able to efficiently generate the frequency tuple simplices

$Lambda_{I/O}^{(N)}(q,k) := Lambda_{I/O}^{0+}(q,k) cap N Delta_B$

where a dilation of the standard simplex is indicated on the RHS. (It will be an implicit corollary of our construction of these sets that the I/O lattice is unimodular, but we do not use this.)

We first define a bucketspace (“$s$ balls in $r$ buckets”) $X_{r,s} := {alpha in mathbb{N}^r : sum_{j=1}^r alpha_j = s}$. Now it is clear that there exists a $B times d$ integer matrix $M^{(Lambda)}$ s.t.

$M^{(Lambda)}X_{B,N} = Lambda_{I/O}^{(N)}(q,k)$

(where the LHS is interpreted in the obvious way). In fact there may be several such integer matrices—each reflecting a particular choice of basis—but all we need is one. We will call it a bucketspace-I/O lattice matrix.

The problem of its construction appears subtle (but perhaps that is because we have focused on explicit examples). A useful heuristic is to invoke the LLL lattice basis reduction algorithm on an integer basis for the I/O kernel, then use the structure of the de Bruijn graph—in particular, a table of its cycles—to improve on LLL. Note that the cycle enumeration for de Bruijn graphs has only been effected for small values of $k$.

In practice there are some subtle considerations, which we sketch in the context of the two specific cases $q = 2$ and $k = 3, 4$. Since the I/O kernel is the span of the dimgraph cycle space (see the sequel), it makes sense to look for a set of cycles corresponding to a “nice” basis. A natural candidate is a reduced basis of positive lattice vectors with minimal length.

Once the simple cycles of the de Bruijn graph are enumerated, it is easy to produce such a positive basis with a greedy algorithm. Start with the cycle representatives as a proto-basis. Now pick one of the remaining simple cycles of minimal weight uniformly at random: if it is linearly independent of the existing proto-basis, add it. Keep going until a basis is formed.

For $q = 2, k = 3$ the 6 simple cycles and corresponding simple cycle vectors are

$(0) leftrightarrow (1,0,0,0,0,0,0,0)^T$

$(001) leftrightarrow (0,1,1,0,1,0,0,0)^T$

$(0011) leftrightarrow (0,1,0,1,1,0,1,0)^T$

$(01) leftrightarrow (0,0,1,0,0,1,0,0)^T$

$(011) leftrightarrow (0,0,0,1,0,1,1,0)^T$

$(1) leftrightarrow (0,0,0,0,0,0,0,1)^T$

and the greedy algorithm produces the unique minimal positive basis

${(0),(001),(01),(011),(1)}$.

Similarly for $q=2, k=4$ we have the 19 simple cycles

$(0),(0001),(0001011),(00010111),(00011),(0001101),(000111),(00011101),(001)$,
$(001011),(0010111),(0011),(001101),(00111),(0011101),(01),(011),(0111),(1)$

and the greedy algorithm produces either of the two minimal positive bases

${(0),(0001),(001),(001011),(0011),(01),(011),(0111),(1)}$

${(0),(0001),(001),(0011),(001101),(01),(011),(0111),(1)}$

Note that the simple vectors of length 5 are rejected by the greedy algorithm, as is the simple vector $(000111)$ of weight 6.

(Notice that Gordan’s lemma implies that the monoid [commutative semigroup with identity and cancellation] of integral points in a lattice cone is finitely generated. This in turn implies that we can use one of the minimal positive bases to produce frequency tuple simplices if we are willing to pay a large overhead factor over a more efficient [if less well-understood] method outlined below.)

By performing elementary column operations it is possible to find a workable bucketspace-I/O lattice matrix by trial and error (of course an algorithm would be preferable, but the cycle decomposition of de Bruijn graphs is known only for small values of $k$, suggesting that such a goal is too lofty). We find by direct experiment with $N = 16$ that the following matrices work:

The columns of the $k = 4$ matrix can be indicated graphically:

Finally, notice that the method outlined essentially boils down to finding the vertices of a frequency tuple simplex—but this appears to be more easily said than done.

...

Now that the I/O condition has been suitably developed, we move on to the question of (strong) connectivity. Let $B$ (with an abusive resue of notation) denote the incidence matrix of a dimgraph $G$. Without bothering to restate the common definition, we simple provide a relevant example: for $q = 2$ and $k = 4$ we have

Notice by way of passing that we can recast the I/O equations as

$B1 = 0$.

It can be shown that $ker B$ is the cycle space of $G$.

In any event it is a standard result for dimgraphs that

$mbox{rank}(B(G)) = |V(G)| - c(G)$

where on the RHS we indicate the number of vertices minus the number of components. In short, the rank of the incidence matrix allows us to judge whether or not the corresponding dimgraph is (strongly) connected.

Our intent here is that a generalized de Bruijn dimgraph has only a single component by definition: although we have not really produced a proper mathematical definition, this intent should suffice for the remainder. Now the requirement on a frequency tuple is that

$|V(alpha)| - mbox{rank}(B(alpha)) = 1$.

The number of vertices is just the number of $(k – 1)$-tuples making an appearance; the rank can be computed by Gaussian elimination. For $q = 2$, it can quickly be seen that the rank is just the number of nonzero components in $(alpha_1,dots,alpha_{B/2-1})$.

With that in hand, define the tuple canonical ensemble (TCE) by

$hat Lambda_{I/O}^{(N)}(q,k) := Lambda_{I/O}^{(N)}(q,k) cap {alpha: |V(alpha)|-mbox{rank}(B(alpha)) = 1}$.

The TCE gives all the frequency tuples for a given length, and no garbage points, although some care is required in its construction.

In conclusion: check to see if a given point is in the TCE. If it is, then use the matrix-tree and BEST theorems (again, ask me how and I'll provide a PDF if I see the comment) to determine its cardinality. Providing an enumeration and selecting $p$ minimal completes the solution to the problem, although I'm not sure about the value of $p$, complexity, etc.

ca.analysis and odes - Are two probability distributions uniquely constrained by the sum of their p-norms?

Here is a proof that Steve's rescaling gives you all solutions, together with the trivial operation of permuting the components of $A$, $B$, and $C$ if you view them as vectors with positive coeifficients. (If you view them this way, then Steve's notation $||A||_p$ is just the usual $p$-norm.)

I first tried what Alekk tried: You can take the limit as $p to infty$ and eventually obtain certain power series expansions in $1/p$. Or you can take the limit $p to 0$ and obtain certain power series expansions in $p$. The problem with both approaches is that the information in the terms of these expansions is complicated. To help understand the second limit, I observed that the two sides of Steve's equation are analytic in $p$, but it only helped so much.

Then I realized that when you have a complex analytic function of one variable, you can get a lot of information from looking at singularities. So let's look at that. Let
$alpha_k = ln a_k$, so that
$$||A||_p = expleft( frac{ln bigl[exp(alpha_1 p) + exp(alpha_2 p) + cdots + exp(alpha_d p) bigr]}{p} right).$$
The expression inside the logarithm has been called an exponential polynomial in the literature, which I'll call $a(p)$. As indicated, $||A||_p$ has a logarithmic singularity when $a(p) = 0$. $||A||_p$ has another kind of singularity when $p = 0$, but won't matter for anything. Also $a(p)$ is an entire function, which means in particular that it is univalent and has isolated zeroes. Also, none of the zeroes of $a(p)$ are on the real axis. Let $b(p)$ and $c(p)$ be the corresponding exponential polynomials for $B$ and $C$.

Suppose that you follow a loop that starts on the positive real axis, encircles an $m$-fold zero of $a(p)$ at $p_0$, and then retraces to its starting point. Then the value of $||A||_p$, which is non-zero for $p > 0$, gains a factor of $exp(2mpi i/p_0)$. Thus Steve's equation is not consistent unless all three of $a(p)$, $b(p)$ and, $c(p)$ have the same zeroes with the same multiplicity. (Since $exp(2mpi i/p_0)$ cannot have norm 1, geometric sequences with this ratio but with different values of $m$ are linearly independent.)

At this point, the problem is solved by a very interesting paper of Ritt, On the zeros of exponential polynomials. Ritt reviews certain results of Tamarkin, Polya, and Schwengler, which imply in particular that if an exponential polynomial $f(z)$ does not have any zeroes, then it is a monomial $f_alpha exp(alpha z)$. Ritt's own theorem is that if $f(z)$ and $g(z)$ are exponential polynomials, and if the roots of $f(z)$ are all roots of $g(z)$ (with multiplicity), then their ratio is another exponential polynomial. Thus in our situation $a(p)$, $b(p)$, and $c(p)$ are all proportional up to a constant and an exponential factor. Thus, $A$, $B$, and $C$ must be the same vectors up to permutation, repetition, and rescaling of the coordinates. Repetition is an operation that hasn't yet been analyzed. If $A^{oplus n}$ denotes the $n$-fold repetition of $A$, then $||A^{oplus n}||_p = n^{1/p}||A||_p$. Again, since geometric sequences with distinct ratios are linearly independent, Steve's equation is not consistent if $A$, $B$, and $C$ are repetitions of the same vector by different amounts.

The same argument works for the generalized equation
$$x_1||A_1||_p + x_2||A_2||_p + cdots + x_n||A_n||_p = 0.$$
The result is that any such linear dependence trivializes, after rescaling the vectors and permuting their coordinates.

Update (by J.O'Rourke): Greg's paper based on this solution was just published:

"Norms as a function of $p$ are linearly
independent in finite dimensions," Amer. Math. Monthly, Vol. 119, No. 7, Aug-Sep 2012, pp. 601-3
(JSTOR link).

fourier analysis - A sum involving sines

Consider a scaled sine function, $sin(2pi x/2^n)$, for some positive integer $n$. For this, I have the following linear combination.

$$ sum_{x=1}^{2^{n-2}} c_x sin(2pi x/2^n).$$
(The upper limit to the sum is $2^{n-2}$.)

The question is whether there exist $c_x in {0, pm 1, pm 2}$, not all $0$, that make the above expression $0$, for infinitely many $n$?

If it helps, the above came up in a computation concerning the discrete Fourier Transform.

cell culture - Hoechst or DAPI for nuclear staining?

The Hoechst 33342 dye is similar to DAPI in that both are UV-excited, minor groove-binding, and emit signals proportional to total DNA content. Both are maximally excited around 355 nm and emit around 460 nm. A UV light source is required, which may harm the cell. However, this is only a risk with Hoechst, as DAPI requires the cells to be fixed and/or permeabilized, which is incompatible with life. DAPI is more stable, but Hoechst is brighter. Both are subject to photo-bleaching after long exposure.

There is another newer DNA dye called DRAQ5 that makes up for all of the issues I mentioned earlier - it is bright, quite photo-stable, can be used in live cell imaging, and its excitation and emission wavelengths are in the far red end of the spectrum, meaning that no UV is needed. I found a good comparison chart at http://www.biostatus.com/product/draq5/live_cell_comparison_chart/ if you're interested. I have no connection to them, by the way, I've just used DRAQ5 a lot in the past.

ag.algebraic geometry - Standard reduction to the artinian local case?

Dear Workitout: The list of comments above is getting unwieldy, so let me post an answer here, now that you have finally identified 1.10.1 in Katz-Mazur as (at least one) source of the question. As I predicted, you'll see that the basic technique to be used adapts to many other settings, and that it is very hard to formulate a "meta-theorem" to cover all cases. The only sure-fire method I know is to read all of sections 8, 9, 11, 12 in EGA IV$_3$ and sections 17 and 18 in EGA IV$_4$, and then it becomes really routine. Maybe there's a better method (well I can think of one, but I won't say it here). I will use the terminology and notation around 1.10.1 from Katz-Mazur without explanation below.

Being a "full set of sections" of $Z/S$ is something which is sufficient to check using the constituents of a single open affine cover of $S$, and also a finite generating set of the coordinate ring of $Z$ over each such open. Thus, by working Zariski-locally on $S$ we may assume $S = {rm{Spec}}(R)$ and that both sides of (1) in KM 1.10.1 have $R$-free coordinate rings (when viewed as finite $R$-schemes), and likewise for their sum (as effective Cartier divisors). Now the assertions (1) and (2) in KM 1.10.1 are identities among finitely many elements of some finite free $R$-modules. For instance, (1) asserts that certain elements in a finite free $R$-module have vanishing image in a finite free $R$-module quotient. This is all now a bunch of identities among finitely many elements of $R$.

OK, finally we come to the part with a real idea. Consider the subring $R_0$ of $R$ generated over $mathbf{Z}$ generated by those finitely many elements. It is noetherian. Now unfortunately your initial algebro-geometric setup over $R$ (the smooth separated finite-type curve $C$, the various effective relative Cartier divisors, etc.) probably does not arise via base change from the exact same setup (including flatness properties!) over $R_0$. But that doesn't matter: what would really be swell is if some noetherian subring of $R$ which contains $R_0$ permits such a descent of the situation. Now express $R$ as the direct limit of its finitely generated $R_0$-subalgebras (all of which are noetherian). Does the entire situation descend to one of those? If it did, we'd be in great shape, since it would then suffice to solve the problem in the case of a noetherian base ring (as that would imply the result over $R$ by suitable base change of the descent from the noetherian subring back up to $R$).

How to implement this strategy of reduction to the noetherian case (after which we'll need to deal with the passage to artin local base with algebraically closed residue field)? OK, so that's where we are all very fortunate that Grothendieck actually wrote out the entire formalism in total detail to handle basically every such situation one could ever want to handle. So it becomes kind of a game in finding the references in EGA (which I admit is hard to do if one doesn't know where to look, but is really easy if one has read the right parts). For your particular situation with some smooth separated curves and some relative effective Cartier divisors, etc., the results you need are: EGA IV$_3$ 8.3.4, 8.9.1, 8.10.5 (e.g., (v)), 9.2.6.1, 11.2.6(ii), and IV$_4$ 17.7.9.

I'm not going to say more about how you combine those references here; that is where I again remind you of your pseudonym.

OK, now $R$ is noetherian (even finite type over $mathbf{Z}$, which is very useful extra stuff to have for other arguments with excellence later in life), and you're trying to prove some finite collection of identities among elements of $R$. To do that it suffices to check in the local rings of $R$, so you can assume $R$ is local. Now a pair of elements of a local noetherian ring are equal if and only if they have equal images in each artinian quotient (Krull intersection theorem). So it suffices to prove the general result over arbitrary artin local rings (really just the artinian quotients of finitely generated $mathbf{Z}$-algebra, so there's no set-theoretic quantification nonsense going on). Now $R$ is artin local. To check an identity in a ring it suffices to do so in a faithfully flat extension ring. So finally we haul out EGA 0$_{rm{III}}$ 10.3.1 to find a faithfully flat artin local extension with an algebraically closed residue field. That's it!

I presume you can now see why anyone who knows how to fill in such arguments never actually writes them out in papers: it is much simpler to say "by standard limit methods from EGA IV$_3$, sections 8,9, etc." (maybe even to be a bit more specific, as K-M are at the beginning of their 1.8.1), and to trust that the reader will pick up the clue that they should read those parts of EGA if they want to understand what is going in such arguments for themself. It is bad when people don't at least mention the relevance of sections 8, 9, etc., but things could be worse (e.g., Grothendieck could have not written EGA, leaving stuff in a complete mess reference-wise).

What roles do "base change" play in algebraic geometry?

It might be a not very specific problem. I just wanna know how much do we rely on the property of "base change closed". In the definition of Grothendieck pretopology, we require a collection of morphisms satisfied the "invariant under base change"

As far as I know, in noncommutative algebra. The flat morphism does not respect to base change in general. I heard from some guys in category theory telling me that the "topology" which satisfied the "base change closed" is called "square topology"(I am not sure whether I spell it in correct way).

My question is: if we do not have the property of "invariant under base change". How much algebraic geometry can we recover? Or Is there a big difference from classcial algebraic geometry?

In fact, I know some work of Kontsevich-Rosenberg on noncommutative algebraic geometry dealing with the topology which is lack of base change property. And they called "quasi-topology". I just wonder know if there are other people in category theory or in algebraic geometry ever considered this question.

Thanks in advance!

examples - Do good math jokes exist?

Test to tell the difference between a Physicist or a Mathematician

Consider the following scenario: A room with a sink at the far end with a working cold water faucet plus a table with the following items on top – small bucket, ring stand, Bunsen burner, and a pack of matches. The problem is to boil water.

If the individual picks up the bucket from the table, walks to the sink and fills the bucket from the faucet, brings it back to the table, sets it on the ring stand, puts the Bunsen burner under the stand, and then lights the burner and waits for the water to boil … this establishes the base line but does not separate which it the Physicist and which is the Mathematician.

Test scenario 2: The bucket is now sitting on the floor under the table and the problem is again to boil water.

If the individual picks up the bucket from under the table, walks directly to the sink and fills the bucket from the faucet, brings it back to the table, sets it on the ring stand, puts the Bunsen burner under the stand, and then lights the burner and waits for the water to boil … this proves that this individual is the Physicist.

However, if the individual picks up the bucket from under the table and places it back on top of the table thus reducing the current problem to a form that they have previously solved … this proves that this individual is the Mathematician.