text:
2 added 1920 characters in body

## Moremotivation

This is a stripped down version of a more complicated problem. Suppose that we have an incoming inventory of $n$ different items with unknown value arriving in an online fashion. We can only keep $k$ items of the $n$ total. The decision to keep an item has to be made at the moment of arrival, and once we decide to keep an item we need to stick to this decision.

The value of i-th item, denoted by $X_i$, is unknown, and revealed when it arrives (before a decision needs to be made). However, we do have a prior for the values; they are drawn independently from an identical distribution $F(\cdot)$. The objective of the problem is designing an online policy that maximizes the expected total value of the assignment.

A useful benchmark, when comparing online policies, is the offline optimal solution. Given a realization of the values $X=\{X_i\}_{i=1}^n$, the optimal value of the offline problem, denoted by $P(X)$, is
\begin{align}P(X) = \max_y &\; \sum_{i=1}^n y_i X_i \\& \sum_{i=1}^n y_i = k, \\& y_i \in \{0,1\}\end{align}In this simple case, the offline optimal solution is to keep the items with the k-th highest values. Equivalently, we have that $P(X) = \sum_{i=n-k+1}^n X_{(i)}$. We are interested in the expected optimal value of offline optimal solution, which is given by $\mathbb{E} P(X) = k \mathbb{E} T_k$.

A simple online policy could instruct us to keep those items with value larger than the $(1-k/n)$-percentile. Such policy can be shown to attain an expected value of $n \mathbb{E} \left[ X \mathbf{1} \{ F(X) \ge 1 - k/n\} \right]$ when $n$ is large.

The results that we want to prove would allows us to upper bound the expected optimal value of the offline problem by a bound that could be attained, asymptotically, by an online policy. This would confirm that our policy is good.

1

# An Upper Bound for the Average of Top Order Statistics

The following problem arises when we try to bound the expected offline optimal value of a simple online assignment problem with random values and unit weights, by its deterministic approximation.

Consider a sequence $\{X_i\}_{i=1}^n$ of non-negative integrable i.i.d. random variables with absolutely continuous c.d.f. $F(x)$. Let $X_{(i)}$ be the $i^{\rm th}$ order statistics, so that $X_{(1)}$ is the minimum of the sequence and $X_{(n)}$ is the maximum. Now, let $T_k$ be the average of the top $k^{\rm th}$ order statistics, that is, $T_k = \frac 1 k \sum_{i=n-k+1}^n X_{(i)}$. We would like to show that the expected value of the average of the top order statistics is upper bounded as follows

$$\mathbb{E} T_{k} \le \mathbb{E} \left[ X | F(X) \ge 1 - k/n \right],$$

where the right hand size is the conditional expectation of X given that it is larger than the $(1-k/n)$-percentile. In order to keep things simple, we may assume that the c.d.f. $F(\cdot)$ is strictly increasing in its domain.

Moreover, we may we fix $\rho \in (0,1)$, and set $k=[\rho n]$; so that we are interested in the average of the top $\rho$ fraction of the sequence. If we scale both $n$ and $k$ to infinity while keeping the ratio $\rho$ fixed, it seems to be the case that the bound is asymptotically tight:

$$\lim_{n \rightarrow \infty} \mathbb{E} T_{[\rho n]} = \mathbb{E} \left[ X | F(X) \ge 1 - \rho \right].$$

Can you show if these results hold? I have done some numerical experiments with a couple of distributions (uniform, truncated normal, exponential) that confirm these results. Any help or pointer would be appreciated.


text:
Measurements of the unsteady temperature fluctuations in the plume region between differentially heated horizontal concentric cylinders are reported. In particular, power spectral density estimates of the temperature fluctuations within the plume show the development and breakdown of the oscillatory plume structure at high Rayleigh number, Rad, by two relatively independent processes: (1) the development of harmonic oscillations related to the dominant plume oscillation frequency, and (2) interactions between the oscillating plume and the adjacent relatively stagnant core flow (shear and entrainment). The harmonic oscillations are shown to be the dominant energy transfer mode at moderate Rad (up to Rad = 108), acting to disperse the plume energy without generating a broadband spectrum. The spectral density estimates show that while a distinct plume oscillation is still present near the inner cylinder at Rad = 109, the plume becomes increasingly turbulent as the outer cylinder is approached. A new correlation for the plume oscillation frequency, which is found to be proportional to $Rad0.5$, is also presented.

1.
Bill
R. G.
, and
Gebhart
B.
,
1979
, “
The Development of Turbulent Transport in a Vertical Natural Convection Boundary Layer
,”
International Journal of Heat and Mass Transfer
, Vol.
22
, pp.
267
277
.
2.
Bishop
E. H.
,
1988
, “
Heat Transfer by Natural Convection of Helium Between Horizontal Isothermal Concentric Cylinders at Cryogenic Temperature
,”
ASME JOURNAL OF HEAT TRANSFER
, Vol.
110
, pp.
109
115
.
3.
Bishop
E. H.
,
Carley
C. T.
, and
Powe
R. R.
,
1968
, “
Natural Convective Oscillatory Flow in Cylindrical Annuli
,”
International Journal of Heat and Mass Transfer
, Vol.
11
, pp.
1741
1752
.
4.
Dai
Z.
,
Tseng
L. K.
, and
Faeth
G. M.
,
1994
, “
Structure of Round, Fully Developed, Buoyant Turbulent Plumes
,”
ASME JOURNAL OF HEAT TRANSFER
, Vol.
116
, pp.
409
417
.
5.
Dai
Z.
,
Tseng
L. K.
, and
Faeth
G. M.
,
1995
, “
Velocity Statistics of Round, Fully Developed, Buoyant Turbulent Plumes
,”
ASME JOURNAL OF HEAT TRANSFER
, Vol.
117
, pp.
138
145
.
6.
Fersner, J. W., 1986, “Natural Convection Between Horizontal Isothermal Concentric Cylinders: The Temperature Field,” M.S. thesis, Clemson University, Clem-son, SC.
7.
Fisher, C. E., 1996, “An Experimental Study of Plume Dynamics in Turbulent Natural Convection in a Horizontal Annulus,” Ph.D. dissertation, The University of Texas at Austin, Austin, TX.
8.
Fisher, C. E., Kohli, A., and Ball, K. S., 1995, “An Experimental Study of High Rayleigh Number Natural Convection in a Horizontal Annulus,” Proceedings of the 30th National Heat Transfer Conference, Vol. 8, I. S. Habib et al., eds., ASME, New York, pp. 69–78.
9.
Fisher, C. E., Kohli, A., and Ball, K. S., 1994, “Measurement of Power Spectral Density in Turbulent Natural Convection using a Laser Doppler Velocimeter,” ASME Paper No. 94-WA/HT-16.
10.
Kuehn
T. H.
, and
Goldstein
R. J.
,
1976
a, “
An Experimental and Theoretical Study of Natural Convection in the Annulus between Horizontal Concentric Cylinders
,”
Journal of Fluid Mechanics
, Vol.
74
, pp.
695
719
.
11.
Kuehn
T. H.
, and
Goldstein
R. J.
,
1976
b, “
Correlating Equations for Natural Convection Heat Transfer between Horizontal Circular Cylinders
,”
International Journal of Heat and Mass Transfer
, Vol.
19
, pp.
1127
1134
.
12.
Kuehn
T. H.
, and
Goldstein
R. J.
,
1978
, “
An Experimental Study of Natural Convection Heat Transfer in Concentric and Eccentric Horizontal Cylindrical Annuli
,”
ASME JOURNAL OF HEAT TRANSFER
, Vol.
100
, pp.
635
640
.
13.
Kuehn
T. H.
, and
Goldstein
R. J.
,
1980
, “
A Parametric Study of Prandtl Number and Diameter Ratio Effects on Natural Convection Heat Transfer in Horizontal Cylindrical Annuli
,”
ASME JOURNAL OF HEAT TRANSFER
, Vol.
102
, pp.
768
770
.
14.
Lis, J., 1966, “Experimental Investigation of Natural Convection Heat Transfer in Simple and Obstructed Horizontal Annuli,” Proceedings of the Third International Heat Transfer Conference, AIChE, New York, pp. 196–204.
15.
McLeod, A. E., 1987, “Heat Transfer by Natural Convection of Helium Between Horizontal Isothermal Concentric Cylinders at Cryogenic Temperatures,” M.S. thesis, Clemson University, Clemson, SC.
16.
McLeod
A. E.
, and
Bishop
E. H.
,
1989
, “
Turbulent Natural Convection of Gases in Horizontal Cylindrical Annuli at Cryogenic Temperatures
,”
International Journal of Heat and Mass Transfer
, Vol.
32
, pp.
1967
1978
.
17.
Moffat
R. J.
,
1982
, “
Contribution to the Theory of Single-Sample Uncertainty Analysis
,”
ASME Journal of Fluids Engineering
, Vol.
104
, pp.
250
258
.
18.
Papanicolaou
P. N.
, and
List
E. J.
,
1987
, “
Statistical and Spectral Properties of Tracer Concentration in Round Buoyant Jets
,”
International Journal of Heat and Mass Transfer
, Vol.
30
, pp.
2059
2071
.
19.
Powe
R. E.
,
Carley
C. T.
, and
Bishop
E. H.
,
1969
, “
Free Convective Flow Patterns in Cylindrical Annuli
,”
ASME JOURNAL OF HEAT TRANSFER
, Vol.
91
, pp.
310
314
.
20.
Sangras
R.
,
Dai
Z.
, and
Faeth
G. M.
,
1998
, “
Mixing Structure of Plane Self-Preserving Buoyant Turbulent Plumes
,”
ASME JOURNAL OF HEAT TRANSFER
, Vol.
120
, pp.
1033
1041
.
21.
Tennekes, H. and Lumley, J. L., 1972, A First Course in Turbulence, MIT Press, Cambridge, MA.
22.
Turner, J. S., 1973, Buoyancy Effects in Fluids, Cambridge University Press, New York.
This content is only available via PDF.

format: plain


text:
Stream: new members

Topic: Discrete topology?

Pedro Minicz (Aug 15 2020 at 22:46):

Where is the definition of the discrete topology on a type α? There is a definition of discrete topology predicate here. It defines it as being equal to the bottom element of some order. I am struggling to make sense of this definition and don't seem to find the definition of the bottom element itself (it is implicitly declared somewhere I believe).

Mario Carneiro (Aug 15 2020 at 22:48):

You could look for #check (by apply_instance : has_bot (topological_space A))

Mario Carneiro (Aug 15 2020 at 22:50):

It looks like it's coming from src#topological_space.complete_lattice, in a bit of abstract nonsense

Mario Carneiro (Aug 15 2020 at 22:52):

In short, it reduces to univ

Pedro Minicz (Aug 15 2020 at 22:56):

Mario Carneiro said:

In short, it reduces to univ

What exactly do you mean it reduces to univ? I know that is_open = univ is this topology, but I don't see how that term can reduce to univ.

Mario Carneiro (Aug 15 2020 at 22:57):

it's pretty involved. Where are you stuck?

Pedro Minicz (Aug 15 2020 at 22:57):

I managed to complete the goal I was working on with a single simp and honestly I am not quite sure how it worked.

Pedro Minicz (Aug 15 2020 at 22:58):

import topology.order
import tactic

variables {α : Type*}

namespace cofinite

@[simp] def is_open : set α  Prop :=
λ s, set.finite (set.univ \ s)  s =

lemma is_open_univ : is_open (set.univ : set α) :=
begin
unfold is_open,
left,
rw set.diff_self,
exact set.finite_empty
end

lemma is_open_inter (s₁ s₂ : set α) :
is_open s₁  is_open s₂  is_open (s₁  s₂) :=
begin
rintros (hs₁ | hs₁) (hs₂ | hs₂),
{ unfold is_open,
left,
rw set.diff_inter,
exact set.finite.union hs₁ hs₂ },
all_goals { right, simp [hs₁, hs₂] }
end

lemma is_open_sUnion (s : set (set α)) (hs :  t, t  s  is_open t) :
is_open (⋃₀ s) :=
begin
by_cases h :  t, t  s  t  ,
{ unfold is_open,
left,
rcases h with t, ht₁, ht₂,
have ht₂ : set.finite (set.univ \ t),
{ cases hs t ht₁ with ht₃ ht₃,
{ exact ht₃ },
{ exfalso, exact ht₂ ht₃ } },
apply set.finite.subset ht₂,
intros x hx,
suffices : x  t, { simpa },
simp at hx,
exact hx t ht₁ },
{ push_neg at h,
unfold is_open,
right,
ext x,
suffices :  t, t  s  x  t, { simpa },
intros t ht,
specialize h t ht,
rw set.eq_empty_iff_forall_not_mem at h,
exact h x }
end

@[simp] instance topological_space (α : Type*) : topological_space α :=
{ is_open := is_open,
is_open_univ := is_open_univ,
is_open_inter := is_open_inter,
is_open_sUnion := is_open_sUnion }

example [fintype α] : discrete_topology α :=
begin
constructor,
ext s,
split; intro hs,
-- I have no idea what the following simp is doing.
{ simp only [topological_space.is_open] at hs },
{ left, apply set.finite.of_fintype }
end

end cofinite

Pedro Minicz (Aug 15 2020 at 22:58):

A bit long, the goal is the last example.

Mario Carneiro (Aug 15 2020 at 22:59):

The simp only is smoke and mirrors, the proof is trivial

Mario Carneiro (Aug 15 2020 at 23:00):

It would be good to have a simp lemma that says \bot.is_open s though

Ah, of course!

Pedro Minicz (Aug 15 2020 at 23:01):

Mario Carneiro said:

It would be good to have a simp lemma that says \bot.is_open s though

Yes, that would be quite convenient.

Pedro Minicz (Aug 15 2020 at 23:02):

Isn't it curious that simp doesn't close the trivial goal?

Kevin Buzzard (Aug 15 2020 at 23:04):

It's not an equality

Floris van Doorn (Aug 15 2020 at 23:55):

simp doesn't unfold definitions, unless it is told to (by attributes or when you invoke it). So simp doesn't know the goal is trivial.

Floris van Doorn (Aug 15 2020 at 23:56):

There are plenty of times when simp doesn't close a goal, but refl or exact trivial does (sometimes that means more things should be simp-lemmas)

Patrick Massot (Aug 16 2020 at 00:00):

docs#is_open_discrete

Mario Carneiro (Aug 16 2020 at 00:35):

The irony is that even though simp proves things by reducing them to true, simp will fail on the goal true

Last updated: May 08 2021 at 10:12 UTC


text:
# hannnnah_j’s Biological Test

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

## Description

hannnnah_j is a teacher in WL High school who teaches biology.

One day, she wants to test m students, thus she arranges n different seats around a round table.

In order to prevent cheating, she thinks that there should be at least k empty seats between every two students.

hannnnah_j is poor at math, and she wants to know the sum of the solutions.So she turns to you for help.Can you help her? The answer maybe large, and you need to mod 1e9+7.

## Input

First line is an integer T(T≤1000).
The next T lines were given n, m, k, respectively.
0 < m < n < 1e6, 0 < k < 1000

## Output

For each test case the output is only one integer number ans in a line.

## Sample Input

2
4 2 6
5 2 1

## Sample Output

0
5

wange2014

## Source

2016 ACM/ICPC Asia Regional Shenyang Online


text:
## February 2, 2010

### Derived Synthetic Differential Geometry

#### Posted by Urs Schreiber

Ordinary synthetic differential geometry – at least the well adapted models – is concerned with 0-truncated generalized spaces that are modeled on smooth loci: the formal duals of finitely generated $C^\infty$-rings.

Under derived synthetic differential geometry I suppose we should want to understand the study of the notions of space that are induced from the geometry (in the sense of geometry for structured $(\infty,1)$-toposes) that is the geometric envelope of the pregeometry constituted by $\mathcal{T} := (C^\infty Ring^{fin})^{op}$, with one of its familiar site structures.

This would seem to be an excellent candidate for the ambient geometry in which most of fundamental physics, as presently conceived, takes place.

Maybe we can chat a bit about it here.

For convenience, I repeat the above paragraph, with hyperlinks to background information included:

Ordinary synthetic differential geometry – at least the well adapted models – is concerned with 0-truncated generalized spaces that are modeled on smooth loci: the formal duals of finitely generated $C^\infty$-rings. Under derived synthetic differential geometry I suppose we should want to understand the study of the notions of space that are induced from the geometry (in the sense of geometry for structured $(\infty,1)$-toposes) that is the geometric envelope of the pregeometry constituted by $\mathcal{T} := (C^\infty Ring^{fin})^{op}$, with one of its familiar site structures.

the approach sketched in the very last paragraph of Structured Spaces and then carried out in some detail in

goes in the direction of derived synthetic differential geometry . But it is different from what is indicated above:

• following Lurie, David Spivak considers, essentially , the pregeometry given by $\mathcal{T} :=$ CartSp. This is the formal dual of free finitely generated $C^\infty$-rings.

• the above suggests to use $\mathcal{T} := (C^\infty Ring^{fin})^{op}$, the formal dual of all finitely generated $C^\infty$-rings.

I understand well how the choice of pregeometry in the above article is motivated, and have no quarrals with that, I also understand that $CartSp$ is not in fact quite a pregeometry, as discussed in the article, and I understand that in the original version of the thesis instead Diff is used, which is a pregeometry and is conjectured to yield an equivalent result as that discussed in the arXiv version. Still, $Diff$ is just a full subcategory $Diff \hookrightarrow (C^\infty Ring^{fin})^{op}$. I just think for the record this is a point that deserves some highlighting, obvious as it may be.

In fact, it would seem that we could go through sections 4.2 and 4.3 of Structured Spaces, and pretty much systematically replace the sites of ordinary rings appearing there by the corresponding sites of $C^\infty$-rings. Can’t we?

Posted at February 2, 2010 11:42 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2163

### Re: Derived ???

Is this derived’ in a new sense or are notions of up to homotopy’ or resolution by a suitably free object hiding here somewhere?

Posted by: jim stasheff on February 3, 2010 1:00 PM | Permalink | Reply to this

### Re: Derived ???

Is this ‘derived’ in a new sense or are notions of ‘up to homotopy’ or resolution by a suitably free object hiding here somewhere?

Thanks for the question, Jim.

I used to complain, here and elsewhere, that the term “derived xyz-geometry” is unfortunate in its undescriptiveness (and not because of the xyz :-). But it has become so well established and popular that I figured if I want to make myself as well understood as possible in the space that I have for a blog entry headline, then I’d better do it that way.

I started writing a reply to your question in the entry higher geometry in the section derived geometry.

You’ll meet old friends there, but now at their home. At their natural home, as one says. ;-)

Posted by: Urs Schreiber on February 3, 2010 2:57 PM | Permalink | Reply to this

### Re: Derived ???

Yes, that helps - it’s the limits of (or unimaginative use of) language that gave me pains. So derived geometry
means a geometric interpretation/analog of derived in the sense of homological resolutions.

Posted by: jim stasheff on February 4, 2010 1:31 PM | Permalink | Reply to this

### Re: Derived ???

derived geometry means a geometric interpretation/analog of derived in the sense of homological resolutions.

Yes, that’s certainly one of the main motivating points: we don’t just want to algebraically form homological resolutions, but we want to interpret the resolutions themselves as dually having a geometric incarnation. This geometry is “derived geometry”.

Posted by: Urs Schreiber on February 4, 2010 2:08 PM | Permalink | Reply to this

### Re: Derived Synthetic Differential Geometry

Could you give us a sense of the difference it might make for synthetic differential geometry working with all finitely generated $C^\infty$-rings rather than just the free ones?

You mention at derived smooth manifold that Spivak is using something related to the Isbell envelope. Todd was indicating to us here that he knew of “a general biclosed bicategory niche into which things like MacNeille completions and Isbell envelopes fit”. I wonder if his niche is relevant to Spivak’s geometry.

Posted by: David Corfield on February 4, 2010 10:26 AM | Permalink | Reply to this

### Re: Derived Synthetic Differential Geometry

Could you give us a sense of the difference it might make for synthetic differential geometry working with all finitely generated $C^\infty$-rings rather than just the free ones?

A free $C^\infty$-ring is one of the form $C^\infty(\mathbb{R}^n)$ – smooth functions on a cartesian space.

So ordinary sheaves on the site of formal duals of free $C^\infty$-rings are sheaves on the category of manifolds. These contain for instance diffeological spaces (as the full subcategory of concrete sheaves), but they do not contain the crucial ingredient of a smooth topos: a nontrivial infinitesimal interval $D = \{x \in R| x^2 = 0\}$.

Similarly, $\infty$-sheaves ($\infty$-stacks) on the category of formal duals of free $C^\infty$-rings are $\infty$-sheaves on the category of manifolds. This contains all $\infty$-Lie groupoids, but not for instance $\infty$-Lie algebroids - which are $\infty$-Lie groupoids with “infinitesimal morphisms”.

These infinitesimal objects enter the picture when we test not just on formal duals of free $C^\infty$-rings, but on all of them. Actually, we don’t need to test on all of them, it is sufficient to test on those that are the product of a free ring with a “Weil algebra”: a smooth ring of functions on an infinitesimal neighbourhood of a point.

Similarly when we pass to derived stacks here, by generalizing our test objects to cosimplicial test objects, i.e. our rings to simplicial rings: “$\infty$-$C^\infty$-rings”, if you wish.

For instance we may want to regard the BV-BRST complex as the Chevalley-Eilenberg algebra of a derived $\infty$-Lie algebroid. As such it exists in $\infty$-stacks on formal duals of simplicial $C^\infty$-rings, but not – I think – in $\infty$-stacks on just formal duals of simplicial free $C^\infty$-rings. Again, it is the notion of infinitesimal that is otherwise missing.

So the geometry $\mathcal{G}$ (in the sense of geometry for structured $(\infty,1)$-toposes) for a derived version of synthetic differential geometry should be the formal duals of simplicial $C^\infty$-rings, or similar.

Once the geometry is fixed, the “locally ringed topological spaces” with respect to it will be topological spaces $X$ with a structure sheaf exhibited by a suitable functor $\mathcal{G} \to Sh_{(\infty,1)}(X)$. That’s supposed to be the same as a suitable functor $\mathcal{T} \to Sh_{(\infty,1)}(X)$ for $\mathcal{T}$ the corresponding pregeometry.

Here formal duals of $C^\infty$-rings would form the pregeometry, and formal duals of simplicial (“derived”) $C^\infty$-rings the geometry.

In David Spivak’s work, essentially, up to some technical subtlety, the pregeometry $\mathcal{T}$ is taken to be the category of manifolds or Cartesian spaces, hence formal duals of free $C^\infty$-rings. Again, not that there is any problem with that, I am just making a remark on this from the point of view of what one might call “derived synthetic differential geometry”.

Of course, one has to be careful about a certain iteration of concepts here:

a $C^\infty$-ring it itself not unlike a “0-truncated structured $\infty$-topos” on the pregeometry of duals to free $C^\infty$-rings: namely a product preserving functor

$CartSp \to Sh(*) = Set \,.$

And it is this perspective that David Spivak varies, by paassing instead to functors

$CartSp \to Sh_{(\infty,1)}(*) = sSet$

($\infty-C^\infty$-rings) and then further to locally $\infty$-$C^\infty$-ringed topological spaces $X$

$CartSp \to Sh_{(\infty,1)}(X)$

that constitute the $\infty$-category $dDiff$ (or $dMan$) of “derived smooth manifolds”.

(I am just sketching the rough outline, saying this with all technical qualifiers fully spelled out takes a bit longer, of course.)

Now, from the perspective of derived synthetic differential geometry, what one could do to get the $\infty$-stacks with notions of infinitesimals that I mentioned at the beginning is to take this now as a new category of test spaces , i.e. to pass now from $\infty$-Lie groupoids/$\infty$-stacks on $Diff$ to $\infty$-stacks on $dDiff$!

There is some iteration process going on, where we bootstrap a notion of generalized spaces in terms of $\infty$-stacks on test spaces that are themselved generalized spaces obtained as $\infty$-stacks on other test spaces. It can get a bit confusing. Which is why I thought this is worth making a remark about.

Posted by: Urs Schreiber on February 4, 2010 11:51 AM | Permalink | Reply to this

### Re: Derived Synthetic Differential Geometry

Derived? meaning??

Posted by: jim stasheff on February 4, 2010 1:26 PM | Permalink | Reply to this

### Re: Derived Synthetic Differential Geometry

Derived? meaning??

It’s supposed to remind you of derived category. But – on the other hand – not too much!

In “derived geometry” derived is meant in the good $(\infty,1)$-categorical sense, whereas in “derived category” it refers to the decategorification to a 1-category of an $(\infty,1)$-category.

Notably, in “derived algebraic geometry” one passes from the category of rings to that of simplicial rings . But by the monoidal Dold-Kan correspondence (Schwede-Schipley), the category of simplicial rings is equivalent to the category of non-negatively graded chain dg-algebras, hence to monoids in the category of chain complexes, whose homotopy category is the derived category of modules. That’s one path to connect the two usages of the word “derived” here.

I wasn’t asked when the term “derived geometry” was established, and I think it not a good choice of term at all. But I can try to say what made people come up with it.

It is in fact a bit ironic, I think, since as far as I am aware the term “derived” dates from a time when it was unclear what exactly, conceptually, one did, and all one knew was that one could somehow derive one category from another (abelian) category. The point of “derived geometry” as understood today is the opposite, now one actually knows what it is going on. Therefore I would have thought the right term to use would have been

• higher geometry

• $\infty$-categorical geometry

or the like. But then, considering $\infty$-stacks on 1-categorical sites such as that of manifolds (as we mention above) or the Nisnevich site of schemes (as in motivic cohomology) is also already higher $\infty$-categorical geometry, but is not called “derived geometry”, because the underlying site is still 1-categorical.

The way the term is used currently is that we say derived geometry when the generalized spaces under consideration are $\infty$-stacks on a genuinely $\infty$-categorical site.

Or better, I think you can read Structured Spaces as follows:

take an ordinary site over which you modeled your ordinary geometry and regard it as a pregeometry $\mathcal{T}$. Then the geometric envelope of this pregeometry is a geometry $\mathcal{G}$. And this may be thought of as encoding the derived geometry of $\mathcal{T}$.

For instance when we start with the pregeometry $\mathcal{T} = (CRing^{fin})^{op}$ that underlies ordinary algebraic geometry, then the corresponding geometric envelope is the site of simplicial commutative rings. This is Structured Spaces, prop 4.2.3.

So I suppose a good way to say it would be that

Passing to derived geometry means passing from a pregeometry to its geometric envelope, in the sense of Structured Spaces .

Posted by: Urs Schreiber on February 4, 2010 2:03 PM | Permalink | Reply to this

### Re: Derived Synthetic Differential Geometry

I think this may be slightly incorrect: the name derived category is not to emphasise being derived as a whole from abelian; it stems from earlier terminology. Namely, the derived category is the natural setup to study and naturally redefine the derived functors in homological algebra (classical derived functors were an earlier notion!), without reference to a particular resolution, its objects are already “prepared”, “derived” and hence suitable for derived functors (for classical derived functors, the derived is from having a connected sequence of cohomology like functors derived from a single functor; in addition the business of differential in complexes may have had to do as well with the choice of terminology by Cartan and Eilenberg). The same purpose and logic is for the derived scheme and derived geometry. Not for being derived from usual geometry, but for being suitable for derived/homotopically correct replacements of non-exact constructions. In the main original purpose of derived geometry, that is, constructing correct moduli spaces, one first constructs some ambient space of cocycles, where the moduli live; then one needs to replace single out by setting up equations/equalizers the right ones. This means taking a limit. To make it correct you take homotopy limit, or derive from the left. Then one sees that there are automorphisms, which are THE reason why Grothendieck (in dispair of abundance of automorphisms in problems he studied) introduced stacks, what means deriving from the right: quotienting by automorphisms, by taking homotopy cofibers. Now derived moduli space obtained is indeed obtained by deriving in the sense of derived functors. And once there all operations are correct derived, internally in this world. Just like total derived functors between the derived categories.

Posted by: Zoran Skoda on February 5, 2010 4:44 AM | Permalink | Reply to this

### Re: Derived Synthetic Differential Geometry

Thanks, Zoran, for amplifying derived functors.

I feel that what you say does not contradict what I said, but rather supports it. Derived functors go between homotopy categories (total ones at least), hence in particular between derived categories. Whether the notion of category or of functor is more fundamental depends maybe on perspective, but I take the point that historically derived functors were considered before derived categories.

Still, my same comment as to the usage of the word “derived” applies. As you say yourself:

its objects are already “prepared”, “derived” and hence suitable for derived functors (for classical derived functors, the derived is from having a connected sequence of cohomology like functors derived from a single functor;

So “derived” originally just meant something like “we can obtain one thing from another thing by deriving the latter from the former in some way”. It’s hard to think of a word more vague for an operation that that it “derives” something. I think it is clear that this comes from from a situation where it was not fully clear what happens conceptually when functors are “derived”.

Posted by: Urs Schreiber on February 5, 2010 10:19 AM | Permalink | Reply to this

### Re: Derived Synthetic Differential Geometry

I’ll vote for Zoran’s treatment since it emphasizes the homotopy/homological aspects. To paraphrase Thom,
a word that means everything means nothing. Or
WS Gilbert: when everyone is somebody, then noones anybody ;-)

Posted by: jim stasheff on February 5, 2010 1:52 PM | Permalink | Reply to this

Post a New Comment


text:
International
Tables for
Crystallography
Volume B
Reciprocal space
Edited by U. Shmueli

International Tables for Crystallography (2010). Vol. B, ch. 5.3, pp. 654-655   | 1 | 2 |

## Section 5.3.2. Comparison between X-rays and neutrons with spin neglected

M. Schlenkera* and J.-P. Guigayb

aLaboratoire Louis Néel du CNRS, BP 166, F-38042 Grenoble Cedex 9, France, and  bEuropean Synchrotron Radiation Facility, BP 220, F-38043 Grenoble, France
Correspondence e-mail:  schlenk@grenoble.cnrs.fr

### 5.3.2. Comparison between X-rays and neutrons with spin neglected

| top | pdf |

#### 5.3.2.1. The neutron and its interactions

| top | pdf |

An excellent introductory presentation of the production, properties and scattering properties of neutrons is available (Scherm & Fåk, 1993, and other papers in the same book). A stimulating review on neutron optics, including diffraction by perfect crystals, has been written by Klein & Werner (1983). X-rays and neutrons are compared in terms of the basic quantities in Table 4.1.3.1 of IT C (2004), where Chapter 4.4 is devoted to neutron techniques.

The neutron is a massive particle for which the values relevant to diffraction are: no electric charge, rest mass , angular momentum eigenvalues along a given direction (spin ) and a magnetic moment of −1.913 nuclear magneton, meaning that its component along a quantization direction z can take eigenvalues . The de Broglie wavelength is where h is Planck's constant () and p is the linear momentum; in the nonrelativistic approximation, which always applies in the context of this chapter, v being the neutron's velocity. The neutron's wavelength, λ, and kinetic energy, , are thus related by , or, in practical units, . Thus, to be of interest for diffraction by materials, neutrons should have kinetic energies in the range to  meV. In terms of the velocity, .

Neutron beams are produced by nuclear reactors or by spallation sources, usually pulsed. In either case they initially have an energy in the MeV range, and have to lose most of it before they can be used. The moderation process involves inelastic interactions with materials. It results in statistical distributions of energy, hence of velocity, close to the Maxwell distribution characteristic of the temperature T of the moderator. Frequently used moderators are liquid deuterium (D2, i.e. 2H2) at 25 K, heavy water (D2O) at room temperature and graphite allowed to heat up to 2400 K; the corresponding neutron distributions are termed cold, thermal and hot, respectively.

The interaction of a neutron with an atom is usually described in terms of scattering lengths or of scattering cross sections. The main contribution corresponding to the nuclear interaction is related to the strong force. The interaction with the magnetic field created by atoms with electronic magnetic moments is comparable in magnitude to the nuclear term.

#### 5.3.2.2. Scattering lengths and refractive index

| top | pdf |

The elastic scattering amplitude for scattering vector s, , is defined by the wave scattered by an object placed at the origin when the incident plane wave is , written as with . In the case of the strong-force interaction with nuclei, the latter can be considered as point scatterers because the interaction range is very small, hence the scattering amplitude is isotropic (independent of the direction of s). It is also independent of λ except in the vicinity of resonances. It is conventionally written as −b so that most values of b, called the scattering length, are positive. A table of experimentally measured values of the scattering lengths b is given in IT C for the elements in their natural form as well as for many individual isotopes. It is apparent that the typical order of magnitude is the fm (femtometre, i.e. , or fermi), that there is no systematic variation with atomic number and that different isotopes have very different scattering lengths, including different signs. The first remark implies that scattering amplitudes of X-rays and of neutrons have comparable magnitudes, because the characteristic length for X-ray scattering (the scattering amplitude for forward scattering by one free electron) is fm, the classical electron radius. The second and third points explain the importance of neutrons in structural crystallography, in diffuse scattering and in small-angle scattering. Scattering of neutrons by condensed matter implies the use of the bound scattering lengths, as tabulated in IT C. The free' scattering length, used in some presentations, is obtained by multiplying the bound scattering lengths by , where A is the mass of the nucleus in atomic units.

A description in terms of an interaction potential is possible using the Fermi pseudo-potential, which in the case of the nuclear interaction with a nucleus at can be written as , where δ denotes the three-dimensional Dirac distribution.

Refraction of neutrons at an interface can be conveniently described by assigning a refractive index to the material, such that the wavenumber in the material, k, is related to that in a vacuum, , by . Here where the sum is over the nuclei contained in volume V. With typical values, n is very close to 1 and is typically of the order of . This small value, in the same range as for X-rays, gives a feeling for the order of magnitude of key quantities of the dynamical theory, in particular the Darwin width as discussed in Chapter 5.1 . It also makes total external reflection possible on materials for which : this is the basis for the neutron guide tubes now installed in most research reactors, as well as for reflectometry.

The notations prevailing in X-ray and in neutron crystallography are slightly different, and the correspondence is very simple: X-ray atomic scattering factors and structure factors are numbers. When multiplied by R, the classical electron radius, they become entirely equivalent to the corresponding quantities in neutron usage, which are lengths. It should be noted that the presence of different isotopes and the effect of nuclear spin (disordered except under very special conditions) give rise to incoherent elastic neutron scattering, which has no equivalent in the X-ray case. The scattering length corresponding to R times the atomic scattering factor for X-rays is therefore the coherent scattering length, , obtained by averaging the scattering length over the nuclear spin state and isotope distribution.

#### 5.3.2.3. Absorption

| top | pdf |

Neutron absorption is related to a nuclear reaction in which the neutron combines with the absorbing nucleus to form a compound nucleus, usually in a metastable state which then decays. The scattering length describing this resonance scattering process depends on the neutron energy and contains an imaginary part associated with absorption in complete analogy with the imaginary part of the dispersion correction for the X-ray atomic scattering factors. The energies of the resonances are usually far above those of interest for crystallography, and the linear absorption coefficient varies approximately as or λ. It is important to note that, except for a very few cases (notably 3He, 6Li, 10B, In, Cd, Gd), the absorption of neutrons is very small compared with that of X-rays, and even more so compared with that of electrons, and can be neglected to a first approximation.

#### 5.3.2.4. Differences between neutron and X-ray scattering

| top | pdf |

There are major differences in the experimental aspects of neutron and X-ray scattering. Neutrons are only available in large facilities, where allocation of beam time to users is made on the basis of applications, and where admittance is restricted because of the hazards which nuclear technology can present in the hands of ill-intentioned users. Because of the radiation shielding necessary, as well as the large size of neutron detectors, neutron-scattering instrumentation is much bulkier than that for X-rays. Neutron beams are in some aspects similar to synchrotron radiation, in particular because in both cases the beams are initially white' and for most applications have to be monochromated. There is, however, a huge difference in the order of magnitudes of the intensities. Neutron beams are weak in comparison with laboratory X-ray sources, and weaker by many orders of magnitude than synchrotron radiation. Also, the beam sources are large in the case of neutrons, since they are essentially the moderators, whereas the source is very small in the case of synchrotron radiation, and this difference again increases the ratio of the brilliances in favour of X-rays. This encourages the use of large specimens in all neutron-scattering work, and makes the extinction problem more important than for X-rays. Furthermore, many experiments that are quick using X-rays become very slow, and give rise to impaired resolution, in the neutron case.

There are also at least two additional aspects of neutron scattering in comparison with X-ray scattering, apart from the effect of the magnetic moment associated with the intrinsic (spin) angular momentum of the neutron. On the one hand, the small velocity of neutrons, compared with the velocity of light, makes time-of-flight measurements possible, both in standard neutron diffraction and in investigations of perfect crystals. Because this velocity is of the same order of magnitude as that of ultrasound, the effect of ultrasonic excitation on neutron diffraction is slightly different from that in the X-ray case. On the other hand, the fact that neutrons have mass and a magnetic moment implies that they can be affected by external fields, such as gravity and magnetic fields, both during their propagation in air or in a vacuum and while being diffracted within crystals (Werner, 1980) (see Section 5.3.5). Experiments completely different from the X-ray case can thus be performed with perfect crystals and with neutron interferometers (see Sections 5.3.6 and 5.3.7.3).

#### 5.3.2.5. Translating X-ray dynamical theory into the neutron case

| top | pdf |

As shown in Chapter 5.1 , the basic equations of dynamical theory, viz Maxwell's equations for the X-ray case and the time-independent Schrödinger equation in the neutron case, have exactly the same form when the effect of the neutron spin can be neglected, i.e. in situations that do not involve magnetism and when no externally applied potential is taken into account. The translation scheme for the scattering factors and structure factors is described above. The one formal difference is that the wavefunction is scalar in the neutron case, hence there is no equivalent to the parallel and perpendicular polarizations of the X-ray situation: C in equation (5.1.2.20 ) of Chapter 5.1 should therefore be set to 1.

The physics of neutron diffraction by perfect crystals is therefore expected to be very similar to that of X-ray diffraction, with the existence of wavefields, Pendellösung effects, anomalous transmission, intrinsic rocking-curve shapes and reflectivity versus thickness behaviour in direct correspondence. All experimental tests of these predictions confirm this view (Section 5.3.6).

Basic discussions of dynamical neutron scattering are given by Stassis & Oberteuffer (1974), Sears (1978), Rauch & Petrascheck (1978) and Squires (1978).

### References

International Tables for Crystallography (2004). Vol. C. Mathematical, Physical and Chemical Tables, edited by E. Prince. Dordrecht: Kluwer Academic Publishers.
Klein, A. G. & Werner, S. A. (1983). Neutron optics. Rep. Prog. Phys. 46, 259–335.
Rauch, H. & Petrascheck, D. (1978). Dynamical neutron diffraction and its application. In Neutron Diffraction, edited by H. Dachs, Topics in Current Physics, Vol. 6 pp. 305–351. Berlin: Springer.
Scherm, R. & Fåk, B. (1993). Neutrons. In Neutron and Synchrotron Radiation for Condensed Matter Studies (HERCULES Course), Vol. 1, edited by J. Baruchel, J. L. Hodeau, M. S. Lehmann, J. R. Regnard & C. Schlenker, pp. 113–143. Les Ulis: Les Editions de Physique and Heidelberg: Springer-Verlag.
Sears, V. F. (1978). Dynamical theory of neutron diffraction. Can. J. Phys. 56, 1261–1288.
Squires, G. L. (1978). Introduction to the Theory of Thermal Neutron Scattering. Cambridge University Press.
Stassis, C. & Oberteuffer, J. A. (1974). Neutron diffraction by perfect crystals. Phys. Rev. B, 10, 5192–5202.
Werner, S. A. (1980). Gravitational and magnetic field effects on the dynamical diffraction of neutrons. Phys. Rev. B, 21, 1774–1789.


text:
# An Easy Problem

Time Limit: 1000MS

Memory Limit: 65536K

## Description

As we known, data stored in the computers is in binary form. The problem we discuss now is about the positive integers and its binary form. Given a positive integer I, you task is to find out an integer J, which is the minimum integer greater than I, and the number of '1's in whose binary form is the same as that in the binary form of I. For example, if "78" is given, we can write out its binary form, "1001110". This binary form has 4 '1's. The minimum integer, which is greater than "1001110" and also contains 4 '1's, is "1010011", i.e. "83", so you should output "83".

## Input

One integer per line, which is I (1 <= I <= 1000000). A line containing a number "0" terminates input, and this line need not be processed.

## Output

One integer per line, which is J.

## Sample Input

1
2
3
4
78
0

## Sample Output

2
4
5
8
83

## Source

POJ Monthly,zby03