text:
## Fox-Neuwirth-Fuks cells, quantum shuffle algebras, and Malle’s conjecture for function fields: a new old paper

I have a new paper up on the arXiv today with TriThang Tran and Craig Westerland, “Fox-Neuwirth-Fuks cells, quantum shuffle algebras, and Malle’s conjecture for function fields.”

There’s a bit of a story behind this, but before I tell it, let me say what the paper’s about. The main result is an upper bound for the number of extensions with bounded discriminant and fixed Galois group of a rational function field F_q(t). More precisely: if G is a subgroup of S_n, and K is a global field, we can ask how many degree-n extensions of K there are whose discriminant is at most X and whose Galois closure has Galois group G. A long-standing conjecture of Malle predicts that this count is asymptotic to c X^a (log X)^b for explicitly predicted exponents a and b. This is a pretty central problem in arithmetic statistics, and in general it still seems completely out of reach; for instance, Bhargava’s work allows us to count quintic extensions of Q, and this result was extended to global fields of any characteristic other than 2 by Bhargava, Shankar, and Wang. But an asymptotic for the number of degree 6 extensions would be a massive advance.

The point of the present paper is to prove upper bounds for counting field extensions in the case of arbitrary G and rational function fields K = F_q(t) with q prime to and large enough relative to |G|; upper bounds which agree with Malle’s conjecture up to the power of log X. I’m pretty excited about this! Malle’s conjecture by now has very robust and convincing heuristic justification, but there are very few cases where we actually know anything about G-extensions for any but very special classes of finite groups G. There are even a few very special cases where the method gives both upper and lower bounds (for instance, A_4-extensions over function fields containing a cube root of 3.)

The central idea, as you might guess from the authors, is to recast this question as a problem about counting F_q-rational points on moduli spaces of G-covers, called Hurwitz spaces; by the Grothendieck-Lefschetz trace formula, we can bound these point counts if we can bound the etale Betti numbers of these spaces, and by comparison between characteristic p and characteristic 0 we can turn this into a topological problem about bounding cohomology groups of the braid group with certain coefficients.

Actually, let me say what these coefficients are. Let c be a subset of a finite group G closed under conjugacy, k a field, and V the k-vectorspace spanned by c. Then $V^{\otimes n}$ is spanned by the set of n-tuples (g_1, … , g_n) in c^n, and this set carries a natural action of the braid group, where twining strand i past strand i+1 corresponds to the permutation

$(g_1, \ldots, g_n) \rightarrow (g_1, \ldots, g_{i+1}, g_{i+1}^{-1} g_i g_{i+1}, \ldots, g_n).$

So for each n we have a representation of the braid group Br_n, and it turns out that everything we desire would be downstream from good bounds on

$\dim H^i(Br_n, V^{\otimes n})$

So far, this is the same strategy (expressed a little differently) than was used in our earlier paper with Akshay Venkatesh to get results towards the Cohen-Lenstra conjecture over F_q(t). That paper concerned itself with the case where G was a (modestly generalized) dihedral group; there was a technical barrier that prevented us from saying anything about more general groups, and the novelty of the present paper is to find a way past that restriction. I’m not going to say very much about it here! I’ll just say it turns out that there’s a really nice way to package the cohomology groups above — indeed, even more generally, whenever V is a braided vector space, you have these braid group actions on the tensor powers, and the cohomology groups can be packaged together as the Ext groups over the quantum shuffle algebra associated to V. And it is this quantum shuffle algebra (actually, mostly its more manageable subalgebra, the Nichols algebra) that the bulk of this bulky paper studies.

But now to the story. You might notice that the arXiv stamp on this paper starts with 17! So yes — we have claimed this result before. I even blogged about it! But… that proof was not correct. The overall approach was the same as it is now, but our approach to bounding the cohomology of the Nichols algebra just wasn’t right, and we are incredibly indebted to Oscar Randall-Williams for making us aware of this.

For the last six years, we’ve been working on and off on fixing this. We kept thinking we had the decisive fix and then having it fall apart. But last spring, we had a new idea, Craig came and visited me for a very intense week, and by the end I think we were confident that we had a route — though getting to the present version of the paper occupied months after that.

A couple of thoughts about making mistakes in mathematics.

• I don’t think we really handled this properly. Experts in the field certainly knew we weren’t standing by the original claim, and we certainly told lots of people this in talks and in conversations, and I think in general there is still an understanding that if a preprint is sitting up on the arXiv for years and hasn’t been published, maybe there’s a reason — we haven’t completely abandoned the idea that a paper becomes more “official” when it’s refereed and published. But the right thing to do in this situation is what we did with an earlier paper with an incorrect proof — replaced the paper on arXiv with a placeholder saying it was inaccurate, and issued a public announcement. So why didn’t we do that? Probably because we were constantly in a state of feeling like we had a line on fixing the paper, and we wanted to update it with a correct version. I don’t actually think that’s a great reason — but that was the reason.
• When you break a bone it never exactly sets back the same way. And I think, having gotten this wrong before, I find it hard to be as self-assured about it as I am about most things I write. It’s long and it’s grainy and it has a lot of moving parts. But we have checked it as much as it’s possible for us to check it, over a long period of time. We understand it and we think we haven’t missed anything and so we think it’s correct now. And there’s no real alternative to putting it out into the world and saying we think it’s correct now.

## Little did I know (real analysis edition)

I just finished teaching Math 521, undergraduate real analysis. I first took on this course as an emergency pandemic replacement, and boy did I not know how much I would like teaching it! You get a variety of students — our second and third year math majors, econ majors aiming for top Ph.D. programs, financial math people, CS people — students learning analysis for all kinds of reasons.

A fun thing about teaching outside my research area is encountering weird little facts I don’t know at all — facts which, were they of equal importance and obscurity and size and about algebra, I imagine I would just know. For instance, I was talking about the strategy of the Riemann integral, before launching into the formal definition, as “you are trying to find a sequence of step functions which are getting closer and closer to f, because step functions are the ones you a priori know how to integrate.” But do Riemann-integrable functions actually have sequences of step functions converging to them uniformly? No! It turns out the class of functions which are uniform limits of step functions is called the regulated functions and an equivalent characterization of regulated functions is that the right and left limits f(x+) and f(x-) exist for any x.

Tagged ,

## Compactness as groupwork

Compactness is one of the hardest things in the undergrad curriculum to teach, I find. It’s very hard for students to grasp that the issue is not “is there a finite collection of open sets that covers K” but rather “for every collection of open sets that covers K, some finite subcollection covers K.” This year I came up with a new metaphor. I asked the students to think about how, when a professor assigns a group project, there’s always a very small subgroup of the students who does all the work. That’s sort of how compactness works! Yes, the professor assigned infinitely many open sets to the project, but actually most of them are not really contributing. And it doesn’t matter if some small set of students could do the project; what matters is that some small group among the students assigned to the project is going to end up doing it! And this seems to happen — my students nodded in agreement — no matter how the professor forms the group.

Tagged ,

## There’s only one thing that I know how to do well

Last week I moderated (virtually) a discussion at Stanford between my poetry friend Stephanie Burt and my category theory friend Emily Riehl, on the topic of “identity” — specifically the question of how, in lyric poetry and in mathematics, one addresses the complex topic of what we do when we identify; whether this means “identifying with” a character in a song or poem or story, or identifying two objects which are not equal but which, in Poincare’s phrase, we “call by the same name.”

What I realized after the fact is that, as in so many other matters, the most succinct formulation is in a They Might Be Giants lyric:

There’s only one thing that I know how to do well
I’ve often been told that you only can do what you know how to do well
And that’s be you,
Be what you’re like,
Be like yourself

Surely this points to three different notions that appeared in the discussion:

• “be you” — to say that you are you is to assert equality
• “be what you’re like” — that is, have exactly the properties that you have and no others — an assertion of indiscernibility
• “be like yourself” — this is the assertion of relation (here denoted a “likeness”) between two entities that licenses us, following Poincare, in calling them by the same name — that is, an assertion of equivalence

And here’s YouTube of the They Might Be Giants song, “Whistling in the Dark.” I remember seeing them play this in the fall of 1989, at the Paradise Rock Club, before the album came out, a song nobody had heard. A revelation!

## Why won’t anyone teach her math?

Lots of discussion in my feeds about this Daily Princetonian piece, “Why won’t anyone teach me math?” by first-year student Abigail Rabieh. She just took Math 202, an intro to linear algebra, and the experience was so lousy she’s done with Princeton math for good. That’s bad!

So what was wrong with Rabieh’s class?

“Though I passed MAT 202 class just fine, my experience in it was miserable. The way the course was run did not at all set up students to succeed — or even learn math. For example, though we were provided with practice problems to prepare for our exams, we were never given solutions. My class consistently begged my professor for these, yet all he could say was that not providing them was departmental policy, and it was out of his control.

This begs the question: what interest does a department have in making it impossible to study? Study materials are given so that students can learn the course material and prepare adequately for the exam. Solution sets are part of this: to properly learn, one needs to be able to identify their mistakes and understand why they are wrong. This struggle was reflected in our exam averages, which were, respectively, in the 50s, the 60s, and the 30s.

I am far from the only person who felt this way about my class. MAT 202 has an abysmal rating of 2.71 on princetoncourses.com during the spring 2020-2021 semester. The evaluations on the Office of the Registrar’s website are no better. Students described the course as “disheartening” and said they “lost a lot of respect for the Math department after taking this course.” The advice that came up again and again in many reviews was: “Don’t take this class unless you have to.”

A lot of math teachers instinctively reacted to this with defensiveness, and I was one of them. After all, what’s so bad here? You hand out practice problems for an exam because you want students to do the problems, not because you want them to read the solutions; the mechanism is that the student works all the problems they can and then asks in office hours or review session about the problems they couldn’t do. I don’t think it’s bad to include solutions, but I would never say that not doing so makes it “impossible to study.” Student evals, well — the literature on their unreliability is so vast and I’m so lazy that I’ll only just vaguely gesture at it. And of course, most people taking Math 202 are not taking it for intellectual broadening, as Rabieh admirably was; they are taking it because somebody told them they had to. That makes the evaluations impossible to compare with those for a course people take on purpose. And as for those exam scores, well — a median in the 30s is too low, that would mean I’d made the exam much too hard. A median in the 60s, on the other hand, seems fine to me, an indication that I’d written a test with real challenges but which people could mostly do.

But you know what? Our students, especially our first year students, don’t know that unless we tell them! A student who got into Princeton, or for that matter a student who got into UW-Madison, has probably never gotten a 60/100 on a test in their entire life. No wonder it’s demoralizing!

We don’t really talk about this stuff when we talk about teaching. We mostly talk about content and logistics; in what order should we present the material, how much should we cover, how many quizzes should we give, what should our grading policy be, should we hand out solution sets for practice problems? That’s how we think about what good teaching is, and that’s how our students think about what good teaching is, and that’s why that’s the language Rabieh reached for in her article when she wanted to explain why she had such a bad time. But I don’t think it’s actually the problem.

I’ll bet her teacher did care. Most of us do. But it often doesn’t show; let’s say it out loud! And strive for a classroom where we’re working as partners towards a goal, not just trying to get to the end without feeling like we’ve failed.

Tagged

## “God, as the Pythagoreans said, is a geometer-but not an algebraist”

A remark of Simone Weil, which I learned from Karen Olsson’s book The Weil Conjectures.

In the original, “Pour moi, je pense bien que Dieu, selon la parole pythagoricienne, est un géomètre perpétuel – mais non pas un algébriste.” Here’s the letter to her brother from which this is taken.

I wanted to write more in Shape about the complicated moral weights people assigned to the difference/tension between algebra and geometry. I wrote a little about what Poincaré thought about it, who saw the two subjects as representing two temperaments, both indispensable, though any given mathematician might possess them in different proportions.

But then there is this, from S.I. Segal’s “Topologists in Hitler’s Germany”

“the … Nazi movement saw “truly German” mathematics as intuitive and tied to nature, often geometrical, and certainly not axiomatic. Axiomatics, “logic chopping”, too great abstraction, was Franco-Jewish.”

It is grimly funny to imagine the Nazi ideologues locating in abstract algebra and the insolubility of certain equations in radicals the ultimate origins of rootless cosmopolitanism.

## Pandemic blog 24: enter the gamma

I blogged last week about how to think about “R_0,” the constant governing epidemic growth, when different people in the network had different transmissibility rates.

Today, inspired by Kai Kupferschmidt’s article in Science, I look another look at what happens when the transmission rates vary a lot among people. And I learned something new! So let me set that down.

First of all, et me make one point which is silly but actually has mathematical content. Suppose 90% of the entire population is entirely immune to the disease, and the other 10% each encounter 20 people, sharing extensive air with each one . Since only 2 of those 20 are going to be susceptible, the dynamics of this epidemic are the same as that of an epidemic with an R_0 of 2. So if you look at the exponential growth at the beginning of the epidemic, you would say to yourself “oh, the growth factor is 2, so that’s R_0, we should hit herd immunity at about 50% and end up covering about 80% of the population,” but no, because the population that’s relevant to the epidemic is only 10% the total population! So, to your surprise, the epidemic would crest at 5% prevalence and die out with only 8% of people having been infected.

So extreme heterogeneity really matters — the final spread of the epidemic can be completely decoupled from R_0 (if what we mean by R_0 is the top eigenvalue like last time, which measures the early-epidemic exponential rate of spread.)

In my last post, I included a graph of how spread looked in non-heterogeneous populations generated by 6×6 random matrices I chose randomly, and the graph showed that the top eigenvalue and the eventual spread were strongly coupled to each other. But if you choose a random 6×6 matrix the entries are probably not actually going to be that far apart! So I think this was a little misleading. If the transmissibility has a really long tail, things may be different, as the silly example shows. What follows is a somewhat less silly example.

The model of heterogeneity used in this famous paper seems to be standard. You take transmissibility to be a random variable drawn from a gamma distribution with mean B and shape parameter k. (I had to look up what this was!) The variance is B^2/k. As k goes to infinity, this approaches a variable which is exactly B with probability 1, but for k close to 0, the variable is often near zero but occasionally much larger than B. Superspreaders!

Just like in the last post, we are going to completely jettison reality and make this into a static problem about components of random graphs. I am less confident once you start putting in rare high-transmission events that these two models stay coupled together, but since the back-of-the-envelope stuff I’m doing here seems to conform with what the epidemiologists are getting, let’s go with it. In case you don’t feel like reading all the way to the end, the punchline is that on these kinds of models, you can have early exponential growth that looks like R_0 is 2 or 3, but an epidemic that peters out with a very small portion of people infected; the “herd immunity is closer than we think” scenario, as seen in this preprint of Gomes et al.

Let’s also stick with the “rank 1” case because it’s what’s in the paper I linked and there are already interesting results there. Write X for our gamma-distributed random variable.

Then, sticking with the notation from the last post, the mean number of transmissions per person, the “average R_0”, is

$(\mathbf{E} X)^2 = B^2$

(I guess I wrote the last post in terms of matrices, where the average R_0 was just the sum of the entries of the matrix A, or $\mathbf{1}^T A \mathbf{1}$; here the “matrix” A should be thought of as a rank 1 thing w w^T where w is a vector with entries sampled from X.)

The top eigenvalue is just the trace of the matrix, since all the other eigenvalues are 0, and that is

${\mathbf E} X^2 = B^2(1+1/k)$.

Note already that this is a lot bigger than the average R_0 when k is small! In particular, there are lots of random graphs of this type which have a giant component but average degree < 2; that’s because they have a lot of isolated vertices, I suppose.

So what’s the size of the giant component in a graph like this? As always we are solving an integral equation

$f = 1 - e^{-Af}$

for a function f on measure space, where A is the “matrix” expressing the transmission. In fact, a function on measure space is just a random variable, and the rank-1 operator A sends Y to E(XY)X. The rank-1-ness means we can turn this into a problem about real numbers inteadd of random variables; we know Af = aX for some real number a; applying A to both sides of the above equation we then have

$aX = \mathbf{E}(X(1-e^{-aX}))X$

or

$a = \mathbf{E}(X(1-e^{-aX}))$

But the latter expectation is something you can explicitly compute for a gamma-distributed variable! It just involves doing some integrals, which I rarely get to do! I’ll spare you the computation but it ends up being

$a = B(1-aB/k)^{-(k+1)}$

which you can just solve for a, and then compute E(1-e^{-aX}) if you want to know the total proportion of the population in the giant component. If k is really small — and Adam Kucharski, et al, back in April, wrote it could be as low as 0.1 — then you can get really small giant components even with a fast exponential rate. For instance, take B = 0.45 and k = 0.1; you get a top eigenvalue of 2.2, not inconsistent with the growth rates we saw for unimpeded COVID, but only 7.3% of the population touched by the infection! Another way to put it is that if you introduce the infection to a random individual, the chance of an outbreak is only 7%. As Lloyd-Smith says in the Nature paper, this is a story that makes “disease extinction more likely and outbreaks rarer but more explosive.” Big eigenvalue decouples from eventual spread.

(By the way, Kucharski’s book, The Rules of Contagion, is really good — already out in the UK, coming out here in the US soon — I blurbed it!)

What’s going on here, of course, is that with k this low, your model is that the large majority of people participate in zero interactions of the type likely to cause transmission. Effectively, it’s not so different from the silly example we started with, where 90% of the population enjoyed natural immunity but the other 10% were really close talkers. So having written all this, I’m not sure I needed to have done all those integrals to make this point. But I find it soothing to while away an hour doing integrals.

I don’t know whether I think k=0.1 is realistic, and of course, as Adam K. explained to me by email, who is a superspreader may change with time and context; so 7% is probably too low, since it’s not like once the infection “uses up” the superspreaders there can’t possibly be any more. Probably the variance of propensity to transmit over time should either actually be modeled dynamically or proxied by letting X be a less strongly skewed distribution representing “time average of propensity to transmit” or something like that.

In any event, this does make me feel much more favorable towards the idea that unmitigated spread would end up infecting less than half of the population, not 80% or more. (It does not make me favorable towards unmitigated spread.)

Tagged , ,

## Pandemic blog 20: R_0, random graphs, and the L_2 norm

People are talking about R_0. It’s the number that you wish were below 1. Namely: it is the number of people, on average, that a carrier of SARS-CoV-2 infects during the course of their illness. All the interventions we’re undertaking are designed to shrink that number. Because if it’s bigger than 1, the epidemic grows exponentially until it infects a substantial chunk of the population, and if it’s smaller, the epidemic dies out.

But not everybody has the same R_0! According to some of the epdemiologists writing about COVID, this matters. It matters, for instance, to the question of how far into the population the infection gets before it starts to burn itself out for lack of new susceptible hosts (“herd immunity”) and to the question of how much of the population eventually falls ill.

Here’s an easy way to see that heterogeneity can make a difference. Suppose your population consists of two towns of the same size with no intermunicipal intercourse whatsoever. The first town has an R_0 of 1.5 and the second an R_0 of 0.3. Then the mean R_0 of the whole population is 0.9. But this epidemic doesn’t die out; it spreads to cover much of the population of Contagiousville.

You can read Tim’s interesting thread yourself, but here’s the main idea. Say your population has size N. You make a graph out of the pandemic by placing an edge between vertices i and j if one of the corresponding people infects the other. (Probably better to set this up in a directed way, but I didn’t.) Or maybe slightly better to say: you place an edge if person i and person j interact in a manner such that, were either to enter the interaction infected, both would leave that way. If one person in this graph gets infected, the reach of the infection is the connected component of the corresponding vertex. So how big is that component?

The simplest way to set this up is to connect each pair of vertices with probability c/n, all such choices made independently. This is an Erdos-Renyi random graph. And the component structure of this graph has a beautiful well-known theory; if c > 1, there is a giant component which makes up a positive proportion of the vertices, and all other components are very small. The size of this component is nx, where x is the unique positive number such that

$x = 1 - e^{-cx}$.

If c < 1, on the other hand, there is no big component, so the pandemic is unlikely to reach much of the population. (Correspondingly, the equation above has no nonzero solution.)

It is fair to be skeptical of this model, which is completely static and doesn’t do anything fancy, but let me just say this — the most basic dynamic model of epidemic spread, the SIR model, has an endstate where the proportion of the population that’s been infected is the unique positive x such that

$x = 1 - e^{-R_0x}$.

Which looks pretty familiar!

Now what happens if you want to take into account that the population isn’t actually an undifferentiated mass? Let’s say, for instance, that your county has a red town and a blue town, each with population n/2. Two people in the red town have a probability of 2/n of being connected, while two people in the blue town have a probability of just 1/n of being connected, and a red-blue pair is connected with probability 1/n. (This kind of random graph is called a stochastic block model, if you want to go look at papers about it.) So the typical red-town person is going to infect 1 fellow red-towner and 0.5 blue-towners, for an R_0 of 1.5, while the blue-towner is going to have an R_0 of 1.

Here’s the heuristic for figuring out the size of the big component. Suppose x is the proportion of the red town in the big component of the graph, and y is the proportion of the blue town in the big component. Take a random red person; what’s the change they’re in the big component? Well, the chance they’re not connected to any of the xn/2 red-towners in the big component is

$(1-2/n)^{xn/2} = e^{-1}$

(oh yeah did I mention that n was infinity?) and the chance that they’re not connected to any of the blue-towners in the big component is

$(1-1/n)^{yn/2} = e^{-(1/2)y}$

so all in all you get

$x = 1 - e^{-(x + (1/2)y}$

and by the same token you would get

$y = 1-e^{-((1/2)x + (1/2)y)}$

and now you have two equations that you can solve for x and y! In fact, you find x = 47% and y = 33%. So just as you might expect, the disease gets farther in the spreadier town.

And you might notice that what we’re doing is just matrix algebra! If you think of (x,y) as a vector v, we are solving

$v = \mathbf{1} - e^{-Av}$

where “exponentiation” of a vector is interpreted coordinatewise. You can think of this as finding a fixed point of a nonlinear operator on vectors.

When does the outbreak spread to cover a positive proportion of the population? There’s a beautiful theorem of Bollobas, Janssen, and Riordan that tells you: you get a big component exactly when the largest eigenvalue λ of A, the so-called Perron-Frobenius eigenvalue, is larger than 1. In the case of the matrix studied above, the two eigenvalues are about 1.31 and 0.19. You might also note that in the early stages of the epidemic, when almost everyone in the network is susceptible, the spread in each town will be governed by repeated multiplication of a small vector by A, and the exponential rate of growth is thus also going to be given by λ.

It would be cool if the big eigenvalue also told you what proportion of the vertices are in the giant component, but that’s too much to ask for. For instance, we could just replace A with a diagonal matrix with 1.31 and 0.19 on the diagonal; then the first town gets 43% infected and the second town completely disconnected from the first, gets 0.

What is the relationship between the Perron-Frobenius eigenvalue and the usual “mean R_0” definition? The eigenvalue can be thought of as

$\max_{v} v^T A v / v^T v$

while the average R_0 is exactly

$\mathbf{1}^T A \mathbf{1} / n$

where 1 is the all-ones vector. So we see immediately that λ is bounded below by the average R_0, but it really can be bigger; indeed, this is just what we see in the two-separated-towns example we started with, where R_0 is smaller than 1 but λ is larger.

I don’t see how to work out any concise description of the size of the giant component in terms of the symmetric matrix, even in the simplest cases. As we’ve seen, it’s not just a function of λ. The very simplest case might be that where A has rank 1; in other words, you have some division of the population into equal sized boxes, and each box has its own R_0, and then the graph is constructed in a way that is “Erdos-Renyi but with a constraint on degrees” — I think there are various ways to do this but the upshot is that the matrix A is rank 1 and its (i,j) entry is R_0(i) R_0(j) / C where C is the sum of the R_0 in each box. The eigenvalues of A are all zero except for the big one λ, which is equal to the trace, which is

$\mathbf{E} R_0^2 / \mathbf{E} R_0$

or, if you like, mean(R_0) + variance(R_0)/mean(R_0); so if the average R_0 is held fixed, this gets bigger the more R_0 varies among the population.

And if you look back at that Wikipedia page about the giant component, you’ll see that this is the exact threshold they give for random graphs with specified degree distribution, citing a 2000 paper of Molloy and Reid. Or if you look at Lauren Meyers’s 2005 paper on epidemic spread in networks, you will find the same threshold for epidemic outbreak in section 2. (The math here is descended from work of Molloy-Reed and this much-cited paper of Newman, Strogatz, and Watts.) Are typical models of “random graphs with specified degree distribution” are built to have rank 1 in this sense? I think so — see e.g. this sentence in Newman-Strogatz-Watts: “Another quantity that will be important to us is the distribution of the degree of the vertices that we arrive at by following a randomly chosen edge. Such an edge arrives at a vertex with probability proportional to the degree of that vertex.”

At any rate, even in this rank 1 case, even for 2×2 matrices, it’s not clear to me how to express the size of the giant component except by saying it’s a nonzero solution of $v = 1 - e^{Av}$. Does the vector v have anything do do with the Perron-Frobenius eigenvector? Challenge for the readers: work this out!

I did try a bunch of randomly chosen 6×6 matrices and plot the overall size of the giant component against λ, and this is what I got:

The blue line shows the proportion of the vertices that get infected if the graph were homogeneous with parameter λ. Which makes me think that thinking of λ as a good proxy for R_0 is not a terrible idea; it seems like a summary statistic of A which is pretty informative about the giant component. (This graph suggests maybe that among graphs with a given λ, the homogeneous one actually has the biggest giant component? Worth checking.)

I should hasten to say that there’s a lot of interest in the superspreader phenomenon, where a very small (probability -> 0) set of vertices has very large (superlinear in n) number of contacts. Meyers works out a bunch of cases like this and I think they are not well modeled by what I’m talking about here. (Update: I wrote another post about this! Indeed, I think the tight connection shown in the chart between λ and size of giant component is not going to persist when there’s extreme heterogeneity of degree.)

A more technical note: the result of Bollobas et al is much more general; there’s no reason the vertices have to be drawn from finitely many towns of equal size; you can instead have the types of vertices drawn from whatever probability space M you like, and then have the probability of an edge between an vertex x and a vertex y be W(x,y) for some symmetric function on M^2; nowadays this is called the “graphon” point of view. Now the matrix is replaced by an operator on functions:

$A_Wf(x) = \int_M f(y)W(x,y)$,

the probability g(x) that a vertex of type x is in the giant component is a solution of the integral equation

$g = 1-e^{-Ag}$

and a giant component exists just when the operator norm $||A_W||_2$ is greater than 1. This is the kind of analysis you’d want to use if you wanted to really start taking geography into account. For instance, take the vertices to be random points in a disc and let W(x,y) be a decreasing function of |x-y|, modeling a network where infection likelihood is a decreasing function of distance. What is the norm of the operator A_W in this case? I’ll bet my harmonic analyst friends know, if any of them are reading this. But I do not.

Update: Now I know, because my harmonic analyst friend Brian Street told me it’s just the integral over W(x,y) over y, which is the same for all y (well, at least it is if we’re on the whole of R^d.) Call that number V. He gave a very nice Fourier-theoretic argument but now that I know the answer I’m gonna explain it in terms of the only part of math I actually understand, 2×2 matrices. Here’s how it goes. In this model, each vertex has the same expected number of neighbors, namely that integral V above. But to say every vertex has the same expected number of neighbors is to say that 1 is an eigenvector for A. If 1 were any eigenvector other than Perron-Frobenius, it would be orthogonal to Perron-Frobenius, which it can’t be because both have positive entries, so it is Perron-Frobenius, so λ = V.

In fact I had noticed this fact in one of the papers I looked at while writing this (that if the matrix had all row-sums the same, the long-term behavior didn’t depend on the matrix) but didn’t understand why until just this minute. So this is kind of cool — if the kind of heterogeneity the network exhibits doesn’t cause different kinds of vertices to have different mean degree, you can just pretend the network is homogeneous with whatever mean R_0 it has. This is a generalization of the fact that two towns with no contact which have the same R_0 can be treated as one town with the same R_0 and you don’t get anything wrong.

## Pandemic blog 11: Why do curves bend?

When you plot the number of reported deaths from COVID on a log scale you get pictures that look like this one, by John Burn-Murdoch at the Financial Times:

A straight line represents exponential growth, which is what one might expect to see in the early days of a pandemic according to baby models. You’ll note that the straight line doesn’t last very long, thank goodness; in just about every country the line starts to bend. Why are COVID deaths concave? There are quite a few possible reasons.

1. Suppression is working. When pandemic breaks out, countries take measures to suppress transmission, and people take their own measures over and above what their governments do. (An analysis by Song Gao of our geography department of cellphone location data shows that Wisconsinites median distance traveled from home decreased by 50% even before the governor issued a stay-at-home order.) That should slow the rate of exponential growth — hopefully, flip it to exponential decay.
2. Change in reporting. Maybe we’re getting better at detecting COVID deaths; if on day 1, only half of COVID deaths were reported as same, while now we’re accurately reporting them all, we’d see a spuriously high slope at the beginning of the outbreak. (The same reasoning applies to the curve for number of confirmed cases; at the beginning, the curve grows faster than the true number of infections as testing ramps up.)
3. COVID is getting less lethal. This is the whole point of “flattening the curve” — with each week that passes, hospitals are more ready, we have more treatment options and fuller knowledge of which of the existing treatments best suits which cases.
4. Infection has saturated the population. This is the most controversial one. The baby model (where by baby I mean SIR) tells you that the curve bends as the number of still-susceptible people starts to really drop. The consensus seems to be we’re nowhere near that yet, and almost everyone (in the United States, at least) is still susceptible. But I guess one should be open to the possibility that there are way more asymptomatic people than we think and half the population is already infected; or that for some reason a large proportion of the population carries natural immunity so 1% of population infected is half the susceptible population.
5. Heterogeneous growth rate. I came across this idea in a post by a physicist (yeah, I know, but it was a good post!) which I can’t find now — sorry, anonymous physicist! There’s not one true exponential growth rate; different places may have different slopes. Just for the sake of argument, suppose a bunch of different locales all start with the same number of deaths, and suppose the rate of exponential growth is uniformly distributed between 0 and 1; then the total deaths at time t is $\int^1_0 e^{\alpha t} d \alpha$ which is $(1/t)(e^t - 1)$. The log of that function has positive second derivative; that is, it tends to make the curve bend up rather than down! That makes sense; with heterogeneous rates of exponential growth, you’ll start with some sort of average of the rates but before long the highest rate will dominate.

I’m sure I’ve skipped some curve-bending factors; propose more in comments!

Tagged , ,

## Commutativity, with fractions

Talking to AB about multiplying rational numbers. She understands the commutativity of multiplication of integers perfectly well. But I had forgotten that commutativity in the rational setting is actually conceptually harder! That four sixes is six fours you can conceptualize by thinking of a rectangular array, or something equivalent to that. But the fact that seven halves is the same thing as seven divided by two doesn’t seem as “natural” to her. (Is that even an instance of commutativity? I think of the first as 7 x 1/2 and the second as 1/2 x 7.)


text:
+1 vote
78 views

If $x+\dfrac{1}{x} = 4$, then what is the value of $x^6 + \dfrac{1}{x^6} ?$

1. $52$
2. $256$
3. $1026$
4. $2702$
edited | 78 views
+1
Answer will be $2702$

$x+\dfrac{1}{x} = 4$

squaring on both sides , we get -

Or, $\left (x+\dfrac{1}{x} \right)^2 = 4^2$

Or, $x^2+\left (\dfrac{1}{x} \right )^2 + 2.x.\dfrac{1}{x} = 16$

Or, $x^2+\left (\dfrac{1}{x} \right )^2 + 2 = 16$

Or, $x^2+\dfrac{1}{x^2}= 16-2 = 14$   ------------------1)

Now, we'll cubing on both sides-

$\left (x^2+\dfrac{1}{x^2} \right)^3 = (14)^3$

Or, $(x^2)^3+\left(\dfrac{1}{x^2}\right)^3 + 3.(x^2)^2.\dfrac{1}{x^2}+3.x^2.\left(\dfrac{1}{x^2}\right)^2 = (14)^3 = 2744$ $\color{purple}{\left [\because (a+b)^3 = a^3+b^3+3a^2b+3ab^2 \right ]}$

Or,  $x^{2 \times 3}+\left(\dfrac{1}{x^{2 \times 3}}\right) + 3.x^{2 \times 2}.\dfrac{1}{x^2}+3.x^2.\left(\dfrac{1}{x^{2 \times 2}}\right) =2744$

Or, $x^{6}+\dfrac{1}{x^{6}} + 3.x^{4}.\dfrac{1}{x^2}+3.x^2.\dfrac{1}{x^{4}}=2744$

Or, $x^{6}+\dfrac{1}{x^{6}} + 3.x^{2}+3.\dfrac{1}{x^{2}}=2744$

Or, $x^{6}+\dfrac{1}{x^{6}} + 3\left (x^{2}+\dfrac{1}{x^{2}} \right )=2744$

Or, $x^{6}+\dfrac{1}{x^{6}} + 3\left (14 \right )=2744$ $\qquad \qquad \left [ \color{Blue }{ \because \text{We know,} \left (x^{2}+\dfrac{1}{x^{2}} \right ) = 14} \color{teal}{\text{ ----from 1)} }\right ]$

Or, $x^{6}+\dfrac{1}{x^{6}} + 42 = 2744$

Or, $\color{Green}{x^{6}+\dfrac{1}{x^{6}}} = 2744-42 = \color{pink}{2702}$
answered by (2.4k points) 4 8 14
selected

format: plain


text:
My Math Forum Help to clarify an issue with Injective function

 Pre-Calculus Pre-Calculus Math Forum

 February 15th, 2017, 12:50 PM #1 Newbie   Joined: Jul 2016 From: Israel Posts: 24 Thanks: 0 Help to clarify an issue with Injective function Hey guys, Can you help me, with how do I know if the following question is an Injective, surjective...etc function? since I have square root and both x1 and x2 are in minus sign, under the square root. Also, when do I know when to reduce my range to R+, R-, R? Thanks in advance!! Last edited by shanytc; February 15th, 2017 at 12:53 PM.
 February 15th, 2017, 02:25 PM #2 Global Moderator   Joined: Dec 2006 Posts: 18,445 Thanks: 1462 What is the domain of f?
 February 15th, 2017, 02:49 PM #3 Newbie   Joined: Jul 2016 From: Israel Posts: 24 Thanks: 0 F(x) = Arccot(x/square root of (1-x squared)) Arccot: R -> (0, PI) Domain is R Range: 0,PI
 February 15th, 2017, 03:15 PM #4 Global Moderator   Joined: Dec 2006 Posts: 18,445 Thanks: 1462 The denominator can't be zero, so the domain can't be R.
February 15th, 2017, 03:26 PM   #5
Newbie

Joined: Jul 2016
From: Israel

Posts: 24
Thanks: 0

Quote:
 Originally Posted by skipjack The denominator can't be zero, so the domain can't be R.
Yes, I know that. I meant R for the definition of arccot.

My question is about the X1 = +-X2, if it narrows the domain even more.

Last edited by skipjack; February 15th, 2017 at 04:31 PM.

 February 15th, 2017, 05:03 PM #6 Global Moderator   Joined: Dec 2006 Posts: 18,445 Thanks: 1462 Okay, but I asked for the domain of f, not arccot. Your equations imply that $x_1 = -x_2$ holds only when both are zero.
February 16th, 2017, 11:08 AM   #7
Newbie

Joined: Jul 2016
From: Israel

Posts: 24
Thanks: 0

Quote:
 Originally Posted by skipjack Okay, but I asked for the domain of f, not arccot. Your equations imply that $x_1 = -x_2$ holds only when both are zero.
Wel, if the denominator can't be zero,
Than the domain must be R+ then.
No?

 February 16th, 2017, 03:24 PM #8 Global Moderator   Joined: Dec 2006 Posts: 18,445 Thanks: 1462 Don't you want the denominator to be real?

 Tags clarify, function, injective, issue

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post benmuskler Real Analysis 3 February 4th, 2017 05:30 PM ach4124 Calculus 2 March 27th, 2015 06:37 PM Senna Real Analysis 2 June 27th, 2014 11:00 PM eraldcoil Abstract Algebra 3 April 24th, 2011 01:38 PM Powermonster Algebra 10 September 30th, 2008 06:51 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top


text:
Hackerrank - Validating Postal Codes Solution
1 min read

# Hackerrank - Validating Postal Codes Solution

A valid postal code have to fullfil both below requirements: must be a number in the range from to inclusive. must not contain more than one alternating repetitive digit pair.

A valid postal code  have to fullfil both below requirements:

1. must be a number in the range from  to  inclusive.
2. must not contain more than one alternating repetitive digit pair.

Alternating repetitive digits are digits which repeat immediately after the next digit. In other words, an alternating repetitive digit pair is formed by two equal digits that have just a single digit between them.

For example:

121426 # Here, 1 is an alternating repetitive digit.
523563 # Here, NO digit is an alternating repetitive digit.
552523 # Here, both 2 and 5 are alternating repetitive digits.

Your task is to provide two regular expressions regex_integer_in_range and regex_alternating_repetitive_digit_pair. Where:

regex_integer_in_range should match only integers range from  to  inclusive

regex_alternating_repetitive_digit_pair should find alternating repetitive digits pairs in a given string.

Both these regular expressions will be used by the provided code template to check if the input string  is a valid postal code using the following expression:

(bool(re.match(regex_integer_in_range, P))
and len(re.findall(regex_alternating_repetitive_digit_pair, P)) < 2)

Input Format

Locked stub code in the editor reads a single string denoting  from stdin and uses provided expression and your regular expressions to validate if  is a valid postal code.

Output Format

You are not responsible for printing anything to stdout. Locked stub code in the editor does that.

Sample Input 0

110000

Sample Output 0

False

Explanation 0

1 1 0000 : (0, 0) and (0, 0) are two alternating digit pairs. Hence, it is an invalid postal code.

Note:
A score of  will be awarded for using 'if' conditions in your code.
You have to pass all the testcases to get a positive score.

### Solution in Python

regex_integer_in_range = r"^[1-9]\d{5}\$"
regex_alternating_repetitive_digit_pair = r"(\d)(?=\d\1)"

import re
P = input()

print (bool(re.match(regex_integer_in_range, P))
and len(re.findall(regex_alternating_repetitive_digit_pair, P)) < 2)

# Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×


text:
Harnack inequality for degenerate balanced random walks

We consider an i.i.d. balanced environment $$\omega(x,e)=\omega(x,-e)$$, genuinely d dimensional on the lattice and show that there exist a positive constant $$C$$ and a random radius $$R(\omega)$$ with streched exponential tail such that every non negative $$\omega$$ harmonic function $$u$$ on the ball $$B_{2r}$$ of radius $$2r>R(\omega)$$, we have $$\max_{B_r} u \leq C \min_{B_r} u$$. Our proof relies on a quantitative quenched invariance principle for the corresponding random walk in balanced random environment and a careful analysis of the directed percolation cluster. This result extends Martin Barlow's Harnack's inequality for i.i.d. bond percolation to the directed case. This is joint work with N. Berger, M. Cohen, and X. Guo.


text:
• ### Announcements

• #### Wondering what's new and changed at GameDev.net?06/20/17

Check out the latest Staff Blog update that talks about what's changed, what's new, and what's up with these "Pixels".
Followers 0

# Efficiently Detecting if objects are out of screen?

## 16 posts in this topic

I have a small optimization problem in my game. If I have 10,000 objects in-game, but only 10 objects on screen (or no objects on screen), the game will lag, because what I do is I check every single frame, for every object, if the object is inside the screen or not.

So obviously as more objects are added, the slower things get. I thought about using some form of spatial indexing, so that if my camera is at (100,100), then instead of looping through 10k objects to know which are in-screen, I will simply ask my grid if there are any objects at 100,100, and do the same for neighbouring cells to get all objects inside the screen without ever having to loop, no matter if I have a thousand, or a million objects.

The problem, however, was that this doesn't account for moving objects, because if an object moves, I would have to check every frame if it has entered another grid cell or exited its cell.

So how do you detect which objects are inside the screen?

0

##### Share on other sites

Quad/Octrees are a good solution (and by far the most used solution to your problem) but you are correct, moving objects are going to have to be updated every frame anyway regardless of octree (but you could do half/quarter step updates on things far away or not recently seen) but in general you should be separating your objects into "dynamic" and "static". That way you only have to loop through your dynamic objects to check for updates, you can even have objects with the ability to change from static to dynamic and back again. (in the case of a physics engine anything with a velocity of 0 you can stop checking if it changed position).

But my bigger concern about your question is the efficiency of your array and culling function. 10k objects/frame is *tiny* on any modern computer you should be pushing millions of ops a second. Probably my first question would be: is this 3D or 2D? Second: can you show us your cull loop?

2

##### Share on other sites

Quadtrees are easy to implement (around 200 lines in Java). Google "quadtree frustrum culling" and you'll probably get some good information about it.

Try not to copy an implementation though. You need to know what is going on the quadtree for doing what you want to do (and for know what else you could do with a quadtree).

Edited by TheChubu
1

##### Share on other sites

The moving object problem isn't that bad. If you think for a while, you'll realize that you'll need to update only objects which move outside of the octree node. So, as long as the object stays inside a node, you don't need to change your spatial structure.

However, depending on the octree implementation, you may need to update the loose bound of nodes (and their parents) which contain moving objects.

Otherwise, if you have objects sparsely, a simple grid might work too. The problem may be that you cannot scale up (ie. increase the visible distance) a grid space spatial structure, since the amount of grid cells increase pretty quickly.

Cheers!

1

##### Share on other sites

In my 2d engine, this is how I chose to solve the problem:

First the interface for a generic spatial container ..

template <typename T>
class SpatialContainer {
public:
virtual bool insert(T item, const Range& boundingBox) = 0;
virtual bool remove(T item, const Range& boundingBox) = 0;
virtual void removeAll() = 0;
virtual int getNumEntries() const = 0;
virtual void getEntries(const Range& region, std::vector<T>& entries) const = 0;
virtual const Range& getBoundary() const = 0;

virtual ~SpatialContainer() {}
};

, where the Range class is just a rectangle, basically.

template <typename T>
class Quadtree : public SpatialContainer<T> {
// (implements the interface defined by SpatialContainer)
};

Then there's the WorldSpace class, which listens for 'entity moved' events and updates its spatial container accordingly. It only manages entities that have first been registered via a call to trackEntity().

class WorldSpace {
public:
inline void init(std::unique_ptr<SpatialContainer<pEntity_t> > container);

inline void trackEntity(pEntity_t entity);
inline void untrackEntity(pEntity_t entity);
inline void untrackAll();
inline void insertEntity(pEntity_t entity);
inline void insertAndTrackEntity(pEntity_t entity);
inline void removeEntity(pEntity_t entity);
inline void removeAndUntrackEntity(pEntity_t entity);
inline void removeAll();
inline void removeAndUntrackAll();
inline void getEntities(const Range& region, std::vector<pEntity_t>& entities) const;

// ...

private:
static std::unique_ptr<SpatialContainer<pEntity_t> > m_container;
static std::set<pEntity_t> m_tracking;

// ...
};

Drawing all on-screen entities is then very simple:

vector<pEntity_t> visibleEnts;
m_worldSpace.getEntities(m_viewArea, visibleEnts);

for (uint_t i = 0; i < visibleEnts.size(); ++i)
visibleEnts[i]->draw();

, where m_viewArea is the rectangle defining the view area.

If you're curious how I implemented the event system, I've written about it here.

Hope this helps

1

##### Share on other sites

I would try first to check if your program is cpu-bound already to not make it worse by complicated sorting on cpu. Then I would use a much simpler approach and just get a rough estimate whats inside the frustum, as the graphics card can do the exact calculations and it will do them anyway.

- Just have a bounding sphere for all objects.

- Calculate the distance of all center points to the frustum one time.

- Sort all objects into 3 buckets

1. inside->test only rarely (few seconds later or whatever)

2. could get inside soon->calc time for next test from (distance-radius)/max possible velocity->save it in the object

3. maybe there are far away things where you have some extra information (get some rough estimate for lower bound of time when they could enter the frustum)

- put some pointers in a priority queue sorted by next test time

- now you just have to retest a few things per frame from the queue when the current time is near the recalculation time you have in the object

Maybe refine this later to use current velocity to get larger retest intervals or velocity vectors to check if objects are moving away from the frustum and not towards it.

That should be easier than immediately going to a complicated datastructure like an octree which you maybe dont even need and could give you problems if you need to split objects at its artificial borders.

1

##### Share on other sites

http://blog.bwhiting.co.uk/?p=362

If you click the link on the page above to go to the demo then press the "+" key to start adding objects, you should see that you can smash though the 10,000 (not on screen but in the world) barrier no sweat barely a millisecond of time on my machine (which isn't amazing or anything)

Not to mention this is actionscript 3, EASILY 10 time slower than most normal languages.

All I am doing is fast frustum culling with caching.

see this post:

http://blog.bwhiting.co.uk/?p=355

b

1

##### Share on other sites
http://blog.bwhiting.co.uk/?p=362

If you click the link on the page above to go to the demo then press the "+" key to start adding objects, you should see that you can smash though the 10,000 (not on screen but in the world) barrier no sweat barely a millisecond of time on my machine (which isn't amazing or anything)

Not to mention this is actionscript 3, EASILY 10 time slower than most normal languages.

All I am doing is fast frustum culling with caching.

see this post:

http://blog.bwhiting.co.uk/?p=355

b

On my crappy computer I get a frame rate of 8 with 10,000 objects. Also, the objects appear 'flat' and unlit; I see no evidence of normal mapping. I think my computer sucks =) .. but this actually makes me happy, because it means that the game I'm developing (in which I'm getting frame rates of around 80) must be performing very well. I think the bottleneck is the fill rate, because when I shrink the window it speeds up considerably.

1

##### Share on other sites

8 FPS is pretty slow, I would wager that it is more your GPU that is slowing it rather than the culling though. (could even be falling back to software as even with 10,000 objects in the scene it should only be rendering about 800 meshes which shouldn't be too stressful)*

The time for culling should be displayed in the upper left (on my machine it would be about 1ms for 10,000 objects occasionally flicking to 2ms)

Forgot to tell you the controls, "m" to change materials, there are a couple in there one is normal mapped, and "n" to change the mesh you can see if how a higer triangle count affects things.

Just read you mentioned fill rate (one day I will learn to read a whole post before replying), this deffo makes sense as when you reduce the window size the culling if anything will have more work to do so yeah probably not an issue.

1

##### Share on other sites

Thanks for all the replies so far!

To confirm, the game I'm working on is a 2D game.

So from what I understand there's really no one perfect solution that is going to fix everything, but combining all these different things to get the performance I need.

So I could implement quad trees, plus this "frustum culling" (which I'm guessing works just as well to 2D games as it does for 3D?)

I could also split my objects into "static" and "dynamic".

I could do as wintertime suggested, and have this sort of "probability" buckets, and not update some objects as much as others depending on how probable it is that they would be in the screen on the next update.

I'm using Lua with Love2D by the way.

0

##### Share on other sites
You then do some frustum culling by starting at the root node (the encompassing box) and recursively checking down through the children of each box. If you can't see a box in your frustum then you will not be able to see any of its children (and hence any objects within it) so it can be discarded. This way you can cull thousands of objects in one simple test.

Just adding to this: the opposite is also true - if a node is fully inside the frustum then all of it's child nodes are also guaranteed to be fully inside the frustum and you can skip testing for them too.  Child nodes only need testing where their parent intersects the frustum.

1

##### Share on other sites
The moving object problem isn't that bad. If you think for a while, you'll realize that you'll need to update only objects which move outside of the octree node. So, as long as the object stays inside a node, you don't need to change your spatial structure.

I wanted to ask about this. Even if the moving object is moving inside one cell, how do I know that? How do I know when it needs to be reassigned to a new node/cell if I'm not constantly checking if it's still within its node?

0

##### Share on other sites

have the entity trigger the recalculation each time it moves. maybe even go as far as have a pointer to the node/cell it's in, so each time it moves it checks if it's still in the same node, and if not, do the recalculation.

0

##### Share on other sites

I'd put something between the object and the data structure that holds the world together. Something that knows what to do with both, like a world manager or something like that. So the object has one object (or a list of 'em) to announce "Hey, I'm moving x units to this way!" And the manger says "Well, let's see what I can do about that buddy!" and they happily lived ever after.

0

##### Share on other sites

[quote name='OmarShehata' timestamp='1357834485' post='5019896']
I wanted to ask about this. Even if the moving object is moving inside one cell, how do I know that? How do I know when it needs to be reassigned to a new node/cell if I'm not constantly checking if it's still within its node?
[/quote]

Each node should have 2 bounds, the strict bound (which comes from the octree subdivision) and the loose bound which is the strict bound + bounds of objects inside the node.

For placing an object inside the octree you should find the node which contains the center point of the objects bound and which isn't smaller than the objects bound.

You know that the object is inside the assigned node by checking the object bounds midpoint vs. nodes strict bound. If the mid point is outside of the bound then you'll need to reassign the object to a new node. Of course your objects needs to be aware in which node it resides.

Cheers!

0

0


text:
## 25 Feb Riemann’s Hypothesis

[Editor: This is the second post in a series about the Millenium Problems. This post is about the Riemann Hypothesis, probably the single most fascinating unsolved problem in all of mathematics. This hypothesis was first proposed by the mathematician Bernhard Riemann. Georg Friedrich Bernhard Riemann (September 17, 1826 – July 20, 1866) was an influential German mathematician who made lasting contributions to analysis and differential geometry, some of them enabling the later development of general relativity.]

The real part (red) and imaginary part (blue) of the Riemann zeta function along the critical line Re(s) = 1/2. The first non-trivial zeros can be seen at Im(s) = ±14.135, ±21.022 and ±25.011.

It all started with Leonard Euler who in 1740 considered the function $zeta(s)$  (the zeta function) given  by the series,

$zeta(s)=1+frac{1}{2^s}+frac{1}{3^s}+ldots$

For $s=1$,  the series diverges and for $s>1$ it converges to give a function called Euler’s zeta function. The importance of this function in number theory became apparent when Euler proved,

$zeta(s)=((1$$2^{-s})^{-1}(1$$3^{-s})^{-1}(1$$5^{-s})^{-1}ldots$

where the product involved all the factors of the form  $(1$$p^{-s})^{-1}$ for every prime $p$. This gives an interesting proof that there are infinite number of primes, because otherwise $zeta(1)$ would have been finite.

Bernhard Riemann, 1863

The connection of zeta function to number theory became more significant when Riemann extended the definition of the function to the whole complex s-plane except $s=1$, where it has a simple pole,  by first using the fact that the series converges for $Re(s)>1$, giving an analytic function in this region and then by using analytic continuation. The extended function is called Riemann’s zeta function. It was found to have zeros at  – 2, -4, -6, …  and these were all the real zeros. Riemann also found that the function must have an infinite number of non-real zeros. Riemann conjectured that all these zeros are of the form $frac{1}{2}+ bi$ i.e. that all these complex zeros lie on the line $Re(z)=frac{1}{2}$ , called the critical line. In 1859 he used the zeta function to investigate the pattern of primes. He hoped that the proof of his conjecture would lead to the proof of a conjecture made by Gauss that the number of primes below any positive integer n is approximately n/ log n and that the approximation becomes better and better as n approaches infinity. However later Hadamard and de la Valle Poussin proved Gauss’s conjecture which came to be known as the Prime Number Theorem, by exploiting the connection between the primes and Riemann’s zeta function without the need of proving Riemann’s conjecture (which is now known as Riemann’s hypothesis). Still if Riemann’s hypothesis is proved it will lead to many other significant  results in analytic number theory.

READ:   Interview with Vint Cerf, VP at Google
The following two tabs change content below.

#### Latest posts by Malay Dutta (see all)

• ##### Peter L. Griffiths
Posted at 22:33h, 31 August Reply

As regards the Riemann hypothesis, very few people seem to know that the non-trivial zeta evaluations discovered by Euler are all terms of the cotangent series. The first term 1/2 becomes Riemann's critical line which apparently converts the zeta evaluations into zero evaluations. It is not just the line which is critical, I confess to being highly critical of the whole process.

• ##### Gonit Sora
Posted at 23:22h, 04 September Reply

Thanks for the info, do keep visiting.

• ##### Peter L. Griffiths
Posted at 22:22h, 21 September Reply

Further to my comment of 31 August 2013, Riemann's 1859 paper is largely based on the more difficult paper by Dirichlet 'There are infinitely many prime numbers in all arithmetic progressions with first term and difference coprime' 1837. Dirichlet needs to be clarified before tackling Riemann.

• ##### Peter L. Griffiths
Posted at 21:28h, 25 September Reply

Dirichlet's paper seems to be proposing a method of generating primes from a simple formula a +nd, where a is 4 and d is 3, and n can be any integer from 1 to infinity. This results in a few composites and omits a few primes, but followers of Riemann seem to think it has possibilities in locating primes which have no roots and hence in locating zeros, which are certainly not the same as zetas.

• ##### Peter L. Griffiths
Posted at 23:03h, 31 October Reply

Further to my previous comments, I have come to the conclusion that Euler's product formula for primes forming the basis of the Riemann hypothesis is wrong. The sum of all numbers can be reconciled with the sum of all primes by systematically deducting the composites from the sum of all numbers, leaving the sum of all primes. The formula quoted by Riemann does not do this.

• ##### Peter L. Griffiths
Posted at 22:51h, 02 November Reply

Further my comment of 31 October 2013, Euler's product formula for primes can be corrected by dividing the Harmonic series by the composite fractions including 1 followed by 1/4 contained in the Harmonic series.

• ##### Peter L. Griffiths
Posted at 22:40h, 03 November Reply

Further to my comment of 2 November 2013 which I accept is difficult to understand. We have to distinguish finite amounts such as the composite fractions from their location which initially may be transfinite, but these composite fractions can be brought together into the finite location dividing the Harmonic series.

• ##### Gonit Sora
Posted at 18:28h, 04 November Reply

Thanks for your comments and interest in this article.

• ##### Peter L. Griffiths
Posted at 23:00h, 05 November Reply

Further to my recent comments, I have come to the conclusion that it is not only all the primes (P) but also all the composites (C) which are deducted from the Harmonic series (H) leaving
1 =H.Product(P-1)/P which is Euler's formula, and not C =H.Product (P-1)/P which is wrong.

• ##### Peter L. Griffiths
Posted at 22:48h, 25 November Reply

This comment I hope delivers the fatal thrust. Near the beginning of his 1859 paper Riemann incorrectly assumes that the complex variable s =1/2 +ti is a Zeta power. Riemann fails to recognise that an expression containing an imaginary number such as 1/2 +ti cannot be a power unless the base is a log base such as e. The best known example of this is Cotes's formula
cosu +isinu equals e^(iu) where it is not possible for e to be meanfully replaced by other values.
This means that Riemann is badly wrong in applying as a power s =1/2 +ti. It also means that all the arguments in his 1859 paper are practically fallacious.

• ##### Peter L. Griffiths
Posted at 21:14h, 19 December Reply

Further to my comment of 25 Novmber 2013, in which I say 'Riemann fails to recognise that an expresion containing an imaginary number such as 1/2 +ti cannot be a power unless the base is e'. I should add 'or its equivalent such as n^(1/logn) which is also always e even though n may be any value'. This makes no difference to my conclusion.

• ##### Peter L. Griffiths
Posted at 21:11h, 23 August Reply

A possible approach to identifying primes could be to apply Euler's discovery H(1-[1/2])(1-[2/3])(1-[4/5])(1-[6/7]) ....=1, where H is the harmonic series 1+(1/2) +(1/3) +(1/5) .... particularly where the series is not carried to infinity.

• ##### Peter L. Griffiths
Posted at 19:54h, 30 August Reply

A Mystery which needs to be solved, why is it that one half the Harmonic series (1/2) +(1/4) +(1/6) .... is not what remains being 1 +(1/3) +(1/5) +(1/7)..... when deducted from the full Harmonic series 1 + (1/2) + (1/3) +(1/4)....The positioning of the terms seems to be important, but the first term 1 needs to be retained to compute the full prime product series.


text:
# torch.use_deterministic_algorithms¶

torch.use_deterministic_algorithms(d)[source]

Sets whether PyTorch operations must use “deterministic” algorithms. That is, algorithms which, given the same input, and when run on the same software and hardware, always produce the same output. When True, operations will use deterministic algorithms when available, and if only nondeterministic algorithms are available they will throw a :class:RuntimeError when called.

Warning

This feature is in beta, and its design and implementation may change in the future.

The following normally-nondeterministic operations will act deterministically when d=True:

The following normally-nondeterministic operations will throw a RuntimeError when d=True:

A handful of CUDA operations are nondeterministic if the CUDA version is 10.2 or greater, unless the environment variable CUBLAS_WORKSPACE_CONFIG=:4096:8 or CUBLAS_WORKSPACE_CONFIG=:16:8 is set. See the CUDA documentation for more details: https://docs.nvidia.com/cuda/cublas/index.html#cublasApi_reproducibility If one of these environment variable configurations is not set, a RuntimeError will be raised from these operations when called with CUDA tensors:

Note that deterministic operations tend to have worse performance than non-deterministic operations.

Parameters

d (bool) – If True, force operations to be deterministic. If False, allow non-deterministic operations.


text:
#### Volume 24, issue 4 (2020)

 Recent Issues
 The Journal About the Journal Editorial Board Editorial Interests Editorial Procedure Subscriptions Submission Guidelines Submission Page Policies for Authors Ethics Statement ISSN (electronic): 1364-0380 ISSN (print): 1465-3060 Author Index To Appear Other MSP Journals
Homological eigenvalues of lifts of pseudo-Anosov mapping classes to finite covers

Geometry & Topology 24 (2020) 1717–1750
##### Abstract

Let $\Sigma$ be a compact orientable surface of finite type with at least one boundary component. Let $f\in Mod\left(\Sigma \right)$ be a pseudo-Anosov mapping class. We prove a conjecture of McMullen by showing that there exists a finite cover $\stackrel{̃}{\Sigma }\to \Sigma$ and a lift $\stackrel{̃}{f}$ of $f$ such that ${\stackrel{̃}{f}}_{\ast }:{H}_{1}\left(\stackrel{̃}{\Sigma },ℤ\right)\to {H}_{1}\left(\stackrel{̃}{\Sigma },ℤ\right)$ has an eigenvalue off the unit circle.

We have not been able to recognize your IP address 34.232.63.94 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

or by using our contact form.

##### Keywords
low-dimensional topology, mapping class groups, representation theory
##### Mathematical Subject Classification 2010
Primary: 20C12, 57M05, 57M60


text:
# [SOLVED] Determining current and drift speed

by octahedron
Tags: current, determining, drift, solved, speed
 P: 39 1. The problem statement, all variables and given/known data The two wires in the above figure are made of the same material. What are the current and the electron drift speed in the 2.0mm-diameter segment of the wire. 2. Relevant equations I = J/A; J = n*e*v_d where n is the density of the conductor in m^-3 and v_d is drift velocity. 3. The attempt at a solution I was able to find the density of the conductor: $$n = \frac{I_{1}}{(Aev_{d_1})} = 2*10^{28}$$ Also, I reached to this relationship between $$I_2$$ and $$v_{d_2}$$: $$I_{2} = 20000v_{d_2}$$ What to do next? Appreciate any pointers, and thanks in advance.
 P: 39 Ah, again, I_2 = I_1. *smacks head* This solves the problem.

 Related Discussions Introductory Physics Homework 2 Introductory Physics Homework 1 Introductory Physics Homework 3 Introductory Physics Homework 1 Introductory Physics Homework 2


text:
# 2019年USAAAO决赛第11题

## 英文题目

11. (25 points)

Cygnus X-1/HDE 226868 is a binary system consisting of a black hole Cygnus X-1 and blue supergiant HDE 226868. The mass of HDE 226868 is 30M@ and the period of the binary system is 5.6 days. Radial velocity data reveals that the orbital velocity of HDE 226868 is 116.68 km/s at apoapse and 123.03 km/s at periapse.

(a) (5 points) Determine the eccentricity of the orbit of HDE 226868.

(b) (5 points) Determine the length of the semimajor axis of the orbit of HDE 226868.

(c) (5 points) Determine the mass of Cygnus X-1, to at least 3 significant figures. The peak blackbody temperature of an accretion disk occurs at a distance of $$r_{peak}$$ and a temperature of $$T_{peak}$$. One can determine the peak blackbody temperature by assuming that it corresponds to the peak in the x-ray spectrum. Due to relativistic effects, the actual peak blackbody temperature $$T_{peak}$$ is related to the peak color temperature Tcolor derived from observed spectral data by $$Tcolor = f_{GR}f_{col}T_{peak}$$, where $$f_{GR} \approx 0.510$$ and $$f_{col} \approx 1.7$$. Three x-ray spectra of Cygnus X-1 are shown in Figure 4.

Figure 4: Three x-ray spectra from Cygnus X-1. From Gou et al. (2011).

(d) (4 points) Using spectrum SP2, determine the peak blackbody temperature $$T_{peak}$$ of the accretion disk around Cygnus X-1.

The total luminosity of the blackbody component of the accretion disk can be estimated by $$L_{disk} \approx 4πσr^2_{pea}kT^4_{peak}$$ (Makishima et al. 1986). The radius $$r_last$$ of the innermost edge of the accretion disk is related to the radius $$r_{peak}$$ of the peak blackbody temperature by $$r_{peak} = ηr_{last}$$, where $$η \approx 0.63$$. In 1996, the blackbody luminosity of the accretion disk around Cygnus X-1 was estimated to be $$2.2 \times 10^{37} ergs/s$$.

(e) (4 points) Determine the radius $$r_{last}$$ of the innermost edge of the accretion disk around Cygnus X-1. Assume that the innermost edge of the accretion disk is located at the innermost stable circular orbit (ISCO), whose radius $$r_{isco}$$ is a function of the spin of the black hole. The relationship between $$r_{isco}$$ and $$a_*$$, the spin parameter of the black hole, can be estimated by: $$r_{isco} =\dfrac{GM^2}{c^2}(\sqrt{8.354 [(2-a_*^2)^2-1]}+1)$$

(f) (2 points) Determine the spin parameter $$a_*$$ of Cygnus X-1.


text:
# Fight for a Dollar

Logic Level 4

Amy and Becca play a game in which they choose an amount to pay ($$A$$ and $$B,$$ respectively). These amounts determine each person's odds of winning the "prize pool" (i.e., Amy wins with odds $$A:B$$ and Becca wins with odds $$B:A$$).

The "prize pool" of this game is the sum of both of the payments plus an additional \$1. How big will the prize pool be if Amy and Becca play according to the pure-strategy Nash Equilibrium of this game?

Assume that they can pay any positive real number amount of money, and give your answer to 3 decimal places.

×


text:
## Journal of Symbolic Logic

### A Spector-Gandy Theorem for $\mathrm{cPC}_d(\mathbb{A})$ Classes

Shaughan Lavine

#### Abstract

Let $\mathfrak{U}$ be an admissible structure. A $\mathrm{cPC}_d(\mathfrak{U})$ class is the class of all models of a sentence of the form $\neg\exists\bar{K} \bigwedge \Phi$, where $\bar{K}$ is an $\mathfrak{U}$-r.e. set of relation symbols and $\phi$ is an $\mathfrak{U}$-r.e. set of formulas of $\mathscr{L}_{\infty\omega}$ that are in $\mathfrak{U}$. The main theorem is a generalization of the following: Let $\mathfrak{U}$ be a pure countable resolvable admissible structure such that $\mathfrak{U}$ is not $\Sigma$-elementarily embedded in $\mathrm{HYP}(\mathfrak{U})$. Then a class $\mathbf{K}$ of countable structures whose universes are sets of urelements is a $\mathrm{cPC}_d(\mathfrak{U})$ class if and only if for some $\Sigma$ formula $\sigma$ (with parameters from $\mathfrak{U}$), $\mathfrak{M}$ is in $\mathbf{K}$ if and only if $\mathfrak{M}$ is a countable structure with universe a set of urelements and $(\mathrm{HYP}_\mathfrak{U}(\mathfrak{M}), \mathfrak{U}, \mathfrak{M}) \models \sigma$, where $\mathrm{HYP}_\mathfrak{U}(\mathfrak{M})$, the smallest admissible set above $\mathfrak{M}$ relative to $\mathfrak{U}$, is a generalization of $\mathrm{HYP}$ to structures with similarity type $\Sigma$ over $\mathfrak{U}$ that is defined in this article. Here we just note that when $\mathrm{L}_\alpha$ is admissible, $\mathrm{HYP}_{\mathrm{L}\alpha}(\mathfrak{M})$ is $\mathrm{L}_\beta(\mathfrak{M})$ for the least $\beta \geq \alpha$ such that $\mathrm{L}_\beta(\mathfrak{M})$ is admissible, and so, in particular, that $\mathrm{HYP}_{\mathbb{HF}}(\mathfrak{M})$ is just $\mathrm{HYP}(\mathfrak{M})$ in the usual sense when $\mathfrak{M}$ has a finite similarity type. The definition of $\mathrm{HYP}_\mathfrak{U}(\mathfrak{M})$ is most naturally formulated using Adamson's notion of a +-admissible structure (1978). We prove a generalization from admissible to +-admissible structures of the well-known truncation lemma. That generalization is a key theorem applied in the proof of the generalized Spector-Gandy theorem.

#### Article information

Source
J. Symbolic Logic, Volume 57, Issue 2 (1992), 478-500.

Dates
First available in Project Euclid: 6 July 2007

https://projecteuclid.org/euclid.jsl/1183743968

Mathematical Reviews number (MathSciNet)
MR1169185

Zentralblatt MATH identifier
0764.03012

JSTOR
Lavine, Shaughan. A Spector-Gandy Theorem for $\mathrm{cPC}_d(\mathbb{A})$ Classes. J. Symbolic Logic 57 (1992), no. 2, 478--500. https://projecteuclid.org/euclid.jsl/1183743968


text:
Volume 385 - 10th International Workshop on Charm Physics (CHARM2020) - Plenary programme
Charmed baryon decays at BESIII
X.R. Lyu* and  On behalf of the BESIII collaboration
Full text: pdf
Pre-published on: September 15, 2021
Published on: November 10, 2021
Abstract
Studies on the weak decays of charmed baryons provide useful information for understanding the interplay of weak and strong interactions in the charm sector.
In 2014, the BESIII experiment accumulated a data set of 567 pb$^{-1}$ at the center-of-mass energy of $\sqrt{s}$=4.6 GeV, an energy point slightly above the $\Lambda^+_c \bar{\Lambda}^-_c$ mass. This is the world first threshold data of the $\Lambda^+_c$ baryon and provides systematical measurements on the production and decay properties of the $\Lambda^+_c$. So far BESIII has published 17 papers of about 30 reaction channels based on the data set taken at 4.6 GeV. In this proceeding, I summarize the BESIII results on the $\Lambda^+_c$ decays in the recent three years. In addition, some prospects on the future programme of charmed baryons are discussed.
DOI: https://doi.org/10.22323/1.385.0016
How to cite

Metadata are provided both in "article" format (very similar to INSPIRE) as this helps creating very compact bibliographies which can be beneficial to authors and readers, and in "proceeding" format which is more detailed and complete.

Open Access


text:
# Rmarkdown template for a Monash working paper

This is only directly relevant to my Monash students and colleagues, but the same idea might be useful for adapting to other institutions.

Some recent changes in the rmarkdown and bookdown packages mean that it is now possible to produce working papers in exactly the same format as we previously used with LaTeX. Continue reading →

# Tourism time series repository

A few years ago, I wrote a paper with George Athanasopoulos and others about a tourism forecasting competition. We originally made the data available as an online supplement to the paper, but that has unfortunately since disappeared although the paper itself is still available.

So I am posting the data here in case anyone wants to use it for replicating our results, or for other research purposes. The data are split into monthly, quarterly and yearly data. There are 366 monthly series, 427 quarterly series and 518 yearly series. Each group of series is further split into training data and test data. Further information is provided in the paper.

If you use the data in a publication, please cite the IJF paper as the source, along with a link to this blog post.

# The latest IJF issue with GEFCom2014 results

The latest issue of the IJF is a bumper issue with over 500 pages of forecasting insights.

The GEFCom2014 papers are included in a special section on probabilistic energy forecasting, guest edited by Tao Hong and Pierre Pinson. This is a major milestone in energy forecasting research with the focus on probabilistic forecasting and forecast evaluation done using a quantile scoring method. Only a few years ago I was having to explain to energy professionals why you couldn’t use a MAPE to evaluate a percentile forecast. With this special section, we now have a tutorial review on probabilistic electric load forecasting by Tao Hong and Shu Fan, which should help everyone get up to speed with current forecasting approaches, evaluation methods and common misunderstandings. The section also contains a large number of very high quality articles showing how to do state-of-the-art density forecasting for electricity load, electricity price, solar and wind power. Moreover, we have some benchmarks on publicly available data sets so future researchers can easily compare their methods against these published results.

In addition to the special section on probabilistic energy forecasting, there is an invited review paper on call centre forecasting by Ibrahim, Ye, L’Ecuyer and Shen. This is an important area in practice, and this paper provides a helpful review of the literature, a summary of the key issues in building good models, and suggests some possible future research directions.

There is also an invited paper from Blasques, Koopman, Łasak and Lucas on “In-sample confidence bands and out-of-sample forecast bands for time-varying parameters in observation-driven models” with some great discussion from Catherine Forbes and Pierre Perron. This was the subject of Siem Jan Koopman’s ISF talk in 2014.

Finally, there are 18 regular contributed papers, more than we normally publish in a whole issue, on topics ranging from forecasting excess stock returns to demographics of households, from forecasting food prices, to evaluating forecasts of counts and intermittent demand. Check them all out on ScienceDirect.

# rOpenSci unconference in Brisbane, 21-22 April 2016

The first rOpenSci unconference in Australia will be held on Thursday and Friday (April 21-22) in Brisbane, at the Microsoft Innovation Centre.

This event will bring together researchers, developers, data scientists and open data enthusiasts from industry, government and university. The aim is to conceptualise and develop R-based tools that address current challenges in data science, open science and reproducibility.

Past examples of the projects can herehere, and here. Also here.

You can view more details, see who else is attending, and most importantly, apply to attend at the website.

# Reproducibility in computational research

Jane Frazier spoke at our research team meeting today on “Reproducibility in computational research”. We had a very stimulating and lively discussion about the issues involved. One interesting idea was that reproducibility is on a scale, and we can all aim to move further along the scale towards making our own research more reproducible. For example

• Can you reproduce your results tomorrow on the same computer with the same software installed?
• Could someone else on a different computer reproduce your results with the same software installed?
• Could you reproduce your results in 3 years time after some of your software environment may have changed?
• etc.

Think about what changes you need to make to move one step further along the reproducibility continuum, and do it.

Jane’s slides and handout are below. Continue reading →

# R vs Autobox vs ForecastPro vs …

Every now and then a commercial software vendor makes claims on social media about how their software is so much better than the forecast package for R, but no details are provided.

There are lots of reasons why you might select a particular software solution, and R isn’t for everyone. But anyone claiming superiority should at least provide some evidence rather than make unsubstantiated claims. Continue reading →

# A new open source data set for detecting time series outliers

Yahoo Labs has just released an interesting new data set useful for research on detecting anomalies (or outliers) in time series data. There are many contexts in which anomaly detection is important. For Yahoo, the main use case is in detecting unusual traffic on Yahoo servers. Continue reading →

# New Australian data on the HMD

The Human Mortality Database is a wonderful resource for anyone interested in demographic data. It is a carefully curated collection of high quality deaths and population data from 37 countries, all in a consistent format with consistent definitions. I have used it many times and never cease to be amazed at the care taken to maintain such a great resource.

The data are continually being revised and updated. Today the Australian data has been updated to 2011. There is a time lag because of lagged death registrations which results in undercounts; so only data that are likely to be complete are included.

Tim Riffe from the HMD has provided the following information about the update:

1. All death counts since 1964 are now included by year of occurrence, up to 2011. We have 2012 data but do not publish them because they are likely a 5% undercount due to lagged registration.
2. Death count inputs for 1921 to 1963 are now in single ages. Previously they were in 5-year age groups. Rather than having an open age group of 85+ in this period counts usually go up to the maximum observed (stated) age. This change (i) introduces minor heaping in early years and (ii) implies different apparent old-age mortality than before, since previously anything above 85 was modeled according to the Methods Protocol.
3. Population denominators have been swapped out for years 1992 to the present, owing to new ABS methodology and intercensal estimates for the recent period.

Some of the data can be read into R using the hmd.mx and hmd.e0 functions from the demography package. Tim has his own package on github that provides a more extensive interface.

# Errors on percentage errors

The MAPE (mean absolute percentage error) is a popular measure for forecast accuracy and is defined as
$$\text{MAPE} = 100\text{mean}(|y_t – \hat{y}_t|/|y_t|)$$
where $y_t$ denotes an observation and $\hat{y}_t$ denotes its forecast, and the mean is taken over $t$.

Armstrong (1985, p.348) was the first (to my knowledge) to point out the asymmetry of the MAPE saying that “it has a bias favoring estimates that are below the actual values”. Continue reading →