text:
chain complex

TheInfoList

In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no general consensus abo ...
, a chain complex is an
algebraic structure In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
that consists of a sequence of
abelian group In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
s (or
modules Broadly speaking, modularity is the degree to which a system's components may be separated and recombined, often with the benefit of flexibility and variety in use. The concept of modularity is used primarily to reduce complexity by breaking a syst ...
) and a sequence of between consecutive groups such that the
image An SAR radar image acquired by the SIR-C/X-SAR radar on board the Space Shuttle Endeavour shows the Teide volcano. The city of Santa Cruz de Tenerife is visible as the purple and white area on the lower right edge of the island. Lava flows ...
of each homomorphism is included in the
kernel Kernel may refer to: Computing * Kernel (operating system) In an operating system with a Abstraction layer, layered architecture, the kernel is the lowest level, has complete control of the hardware and is always in memory. In some systems it ...
of the next. Associated to a chain complex is its Homology (mathematics), homology, which describes how the images are included in the kernels. A cochain complex is similar to a chain complex, except that its homomorphisms are in the opposite direction. The homology of a cochain complex is called its cohomology. In algebraic topology, the singular chain complex of a topological space X is constructed using continuous function#continuous functions between topological spaces, continuous maps from a simplex to X, and the homomorphisms of the chain complex capture how these maps restrict to the boundary of the simplex. The homology of this chain complex is called the singular homology of X, and is a commonly used topological invariant, invariant of a topological space. Chain complexes are studied in homological algebra, but are used in several areas of mathematics, including abstract algebra, Galois theory, differential geometry and algebraic geometry. They can be defined more generally in abelian categories.

# Definitions

A chain complex $\left(A_\bullet, d_\bullet\right)$ is a sequence of abelian groups or modules ..., ''A''0, ''A''1, ''A''2, ''A''3, ''A''4, ... connected by homomorphisms (called boundary operators or differentials) , such that the composition of any two consecutive maps is the zero map. Explicitly, the differentials satisfy , or with indices suppressed, . The complex may be written out as follows. ::$\cdots \xleftarrow A_0 \xleftarrow A_1 \xleftarrow A_2 \xleftarrow A_3 \xleftarrow A_4 \xleftarrow \cdots$ The cochain complex $\left(A^\bullet, d^\bullet\right)$ is the dual (category theory), dual notion to a chain complex. It consists of a sequence of abelian groups or modules ..., ''A''0, ''A''1, ''A''2, ''A''3, ''A''4, ... connected by homomorphisms satisfying . The cochain complex may be written out in a similar fashion to the chain complex. ::$\cdots \xrightarrow A^0 \xrightarrow A^1 \xrightarrow A^2 \xrightarrow A^3 \xrightarrow A^4 \xrightarrow \cdots$ The index ''n'' in either ''A''''n'' or ''A''''n'' is referred to as the degree (or dimension). The difference between chain and cochain complexes is that, in chain complexes, the differentials decrease dimension, whereas in cochain complexes they increase dimension. All the concepts and definitions for chain complexes apply to cochain complexes, except that they will follow this different convention for dimension, and often terms will be given the prefix ''co-''. In this article, definitions will be given for chain complexes when the distinction is not required. A bounded chain complex is one in which almost all#cardinality, almost all the ''A''''n'' are 0; that is, a finite complex extended to the left and right by 0. An example is the chain complex defining the simplicial homology of a finite simplicial complex. A chain complex is bounded above if all modules above some fixed degree ''N'' are 0, and is bounded below if all modules below some fixed degree are 0. Clearly, a complex is bounded both above and below if and only if the complex is bounded. The elements of the individual groups of a (co)chain complex are called (co)chains. The elements in the kernel of ''d'' are called (co)cycles (or closed elements), and the elements in the image of ''d'' are called (co)boundaries (or exact elements). Right from the definition of the differential, all boundaries are cycles. The ''n''-th (co)homology group ''H''''n'' (''H''''n'') is the group of (co)cycles modulo (jargon)#structures, modulo (co)boundaries in degree ''n'', that is, ::$H_n = \ker d_/\mbox d_ \quad \left\left(H^n = \ker d^/\mbox d^ \right\right)$

## Exact sequences

An exact sequence (or exact complex) is a chain complex whose homology groups are all zero. This means all closed elements in the complex are exact. A short exact sequence is a bounded exact sequence in which only the groups ''A''''k'', ''A''''k''+1, ''A''''k''+2 may be nonzero. For example, the following chain complex is a short exact sequence. :$\cdots \xrightarrow \; 0 \; \xrightarrow \; \mathbf \; \xrightarrow \; \mathbf \twoheadrightarrow \mathbf/p\mathbf \; \xrightarrow \; 0 \; \xrightarrow \cdots$ In the middle group, the closed elements are the elements pZ; these are clearly the exact elements in this group.

## Chain maps

A chain map ''f'' between two chain complexes $\left(A_\bullet, d_\right)$ and $\left(B_\bullet, d_\right)$ is a sequence $f_\bullet$ of homomorphisms $f_n : A_n \rightarrow B_n$ for each ''n'' that commutes with the boundary operators on the two chain complexes, so $d_ \circ f_n = f_ \circ d_$. This is written out in the following commutative diagram. : A chain map sends cycles to cycles and boundaries to boundaries, and thus induces a map on homology $\left(f_\bullet\right)_*:H_\bullet\left(A_\bullet, d_\right) \rightarrow H_\bullet\left(B_\bullet, d_\right)$. A continuous map ''f'' between topological spaces ''X'' and ''Y'' induces a chain map between the singular chain complexes of ''X'' and ''Y'', and hence induces a map ''f''* between the singular homology of ''X'' and ''Y'' as well. When ''X'' and ''Y'' are both equal to the n-sphere, ''n''-sphere, the map induced on homology defines the Degree of a continuous mapping#From Sn to Sn, degree of the map ''f''. The concept of chain map reduces to the one of boundary through the construction of the Mapping cone (homological algebra), cone of a chain map.

## Chain homotopy

A chain homotopy offers a way to relate two chain maps that induce the same map on homology groups, even though the maps may be different. Given two chain complexes ''A'' and ''B'', and two chain maps , a chain homotopy is a sequence of homomorphisms such that . The maps may be written out in a diagram as follows, but this diagram is not commutative. : The map ''hd''''A'' + ''d''''B''''h'' is easily verified to induce the zero map on homology, for any ''h''. It immediately follows that ''f'' and ''g'' induce the same map on homology. One says ''f'' and ''g'' are chain homotopic (or simply homotopic), and this property defines an equivalence relation between chain maps. Let ''X'' and ''Y'' be topological spaces. In the case of singular homology, a homotopy between continuous maps induces a chain homotopy between the chain maps corresponding to ''f'' and ''g''. This shows that two homotopic maps induce the same map on singular homology. The name "chain homotopy" is motivated by this example.

# Examples

## Singular homology

Let ''X'' be a topological space. Define ''C''''n''(''X'') for Natural number, natural ''n'' to be the free abelian group formally generated by singular homology, singular n-simplices in ''X'', and define the boundary map $\partial_n: C_n\left(X\right) \to C_\left(X\right)$ to be ::$\partial_n : \, \left(\sigma: \left[v_0,\ldots,v_n\right] \to X\right) \mapsto \left(\sum_^n \left(-1\right)^i \sigma: \left[v_0,\ldots, \hat v_i, \ldots, v_n\right] \to X\right)$ where the hat denotes the omission of a vertex (geometry), vertex. That is, the boundary of a singular simplex is the alternating sum of restrictions to its faces. It can be shown that ∂2 = 0, so $\left(C_\bullet, \partial_\bullet\right)$ is a chain complex; the singular homology $H_\bullet\left(X\right)$ is the homology of this complex. Singular homology is a useful invariant of topological spaces up to homotopy#homotopy equivalence, homotopy equivalence. The degree zero homology group is a free abelian group on the connected space#Path connectedness, path-components of ''X''.

## de Rham cohomology

The differential form, differential ''k''-forms on any smooth manifold ''M'' form a real number, real vector space called Ω''k''(''M'') under addition. The exterior derivative ''d'' maps Ω''k''(''M'') to Ω''k''+1(''M''), and ''d'' = 0 follows essentially from symmetry of second derivatives, so the vector spaces of ''k''-forms along with the exterior derivative are a cochain complex. :$\Omega^0\left(M\right)\ \stackrel\ \Omega^1\left(M\right) \to \Omega^2\left(M\right) \to \Omega^3\left(M\right) \to \cdots$ The cohomology of this complex is called the de Rham cohomology of ''X''. The homology group in dimension zero is isomorphic to the vector space of locally constant functions from ''M'' to R. Thus for a compact manifold, this is the real vector space whose dimension is the number of connected components of ''M''. smoothness#smooth functions between manifolds, Smooth maps between manifolds induce chain maps, and smooth homotopies between maps induce chain homotopies.

# Category of chain complexes

Chain complexes of ''K''-modules with chain maps form a category (mathematics), category Ch''K'', where ''K'' is a commutative ring. If ''V'' = ''V''$_*$ and ''W'' = ''W''$_*$ are chain complexes, their tensor product $V \otimes W$ is a chain complex with degree ''n'' elements given by :$\left(V \otimes W\right)_n = \bigoplus_ V_i \otimes W_j$ and differential given by : $\partial \left(a \otimes b\right) = \partial a \otimes b + \left(-1\right)^ a \otimes \partial b$ where ''a'' and ''b'' are any two homogeneous vectors in ''V'' and ''W'' respectively, and $\left, a\$ denotes the degree of ''a''. This tensor product makes the category Ch''K'' into a symmetric monoidal category. The identity object with respect to this monoidal product is the base ring ''K'' viewed as a chain complex in degree 0. The braided monoidal category, braiding is given on simple tensors of homogeneous elements by :$a \otimes b \mapsto \left(-1\right)^ b \otimes a$ The sign is necessary for the braiding to be a chain map. Moreover, the category of chain complexes of ''K''-modules also has closed monoidal category, internal Hom: given chain complexes ''V'' and ''W'', the internal Hom of ''V'' and ''W'', denoted Hom(''V'',''W''), is the chain complex with degree ''n'' elements given by $\Pi_\text_K \left(V_i,W_\right)$ and differential given by : $\left(\partial f\right)\left(v\right) = \partial\left(f\left(v\right)\right) - \left(-1\right)^ f\left(\partial\left(v\right)\right)$. We have a natural isomorphism :$\text\left(A\otimes B, C\right) \cong \text\left(A,\text\left(B,C\right)\right)$

# Further examples

*Amitsur complex *A complex used to define Bloch's higher Chow groups *Buchsbaum–Rim complex *Čech complex *Cousin complex *Eagon–Northcott complex *Gersten complex *Graph complexhttps://ncatlab.org/nlab/show/graph+complex *Koszul complex *Moore complex *Schur complex


text:
# Another LU decomposition by hand!

edited February 2 in Problems

This problem is just like this one - it's just another version so you can have more practice!

Compute the LU Decomposition of
$$A = \left( \begin{array}{ccc} 1 & 2 & -2 \\ -3 & -7 & 5 \\ -1 & -3 & 2 \end{array} \right)$$
and use this to solve the system $A\vec{x} = \langle 0, 0, 1 \rangle$.

• edited February 4

To obtain the matrix $U$ I used the row operations:
$3R_1+R_2\\ R_1+R_3 \\ -R_2+R_3 \\$
on $A$ with the result
$$U= \ \left[ \begin{array}{ccc} 1 & 2 & -2 \\ 0 & -1 & -1\\ 0 & 0 & 1\\ \end{array} \right] \$$
As usual $L$ is made from the coefficients on the scaled row from the rows operations, but with the opposite sign. $L$ also has 1s on its diagonal. The result is:
$$L= \ \left[ \begin{array}{ccc} 1 & 0 & 0 \\ -3 & 1 & 0\\ -1 & 1 & 1\\ \end{array} \right] \$$
Now to solve $\langle 0,0, 1\rangle$ I used no operations for L as forward row operations have no effect on the vector. Next augmenting it on $U$ and using the operations:
$R_3+R_2 \\ 2R_3+R_1 \\ 2R_2+R_1 \\ -R_2 \\$
resulted in:
$$\ \left[ \begin{array}{ccc|c} 1 & 0 & 0 & 4\\ 0 & 1 & 0 & -1\\ 0 & 0 & 1 & 1\\ \end{array} \right] \$$

• Interesting - Note that I gave this a "Good answer" vote, rather than a "THE Answer" vote. Generally, forward/back substitution is more efficient than a full reduction to reduced row echelon form like this.

• edited February 9

$$A = \begin{pmatrix} 1 & 2 & -2\\ -3 & -7 & 5\\ -1 & -3 & 2 \end{pmatrix}\\$$

Use row operations to get into upper triangular form:

$$(1)R_1 + R_3 \\ \big{(} -(1) = L_{31} \big{)}$$

$$\begin{pmatrix} 1 & 2 & -2 \\ -3 & -7 & 5 \\ 0 & -1 & 0 \end{pmatrix}\\$$

$$(3)R_1 + R_2 \\ \big{(} -(3) = L_{21} \big{)}$$

$$\begin{pmatrix} 1 & 2 & -2 \\ 0 & -1 & -1 \\ 0 & -1 & 0 \end{pmatrix}\\$$

$$(-1)R_2 + R_3 \\ \big{(} -(-1) = L_{32} \big{)}$$

$$\boxed{U = \begin{pmatrix} 1 & 2 & -2 \\ 0 & -1 & -1 \\ 0 & 0 & 1 \end{pmatrix}}\\$$

Construct L matrix,

$$\boxed{L = \begin{pmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ -1 & 1 & 1 \end{pmatrix}}\\$$

Use L and U to solve for $\vec{x}$ :

$$A \vec{x} = LU \vec{x} = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}\\$$

$$\vec{c} = U \vec{x} \\$$

$$L \vec{c} = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \\$$

$$\begin{pmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ -1 & 1 & 1 \end{pmatrix} \begin{pmatrix} a \\ b \\ c \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}\\$$

$$\vec{c} = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}\\$$

$$U \vec{x} = \vec{c}$$

$$\begin{pmatrix} 1 & 2 & -2 \\ 0 & -1 & -1 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}\\$$

$$\boxed{\vec{x} = \begin{pmatrix} 4 \\ -1 \\ 1 \end{pmatrix}}$$

format: plain


text:
Math Help - Points of Symmetry and Turning Points

1. Points of Symmetry and Turning Points

The formula for findintg the x-coordinate of the point of symmetry of a cubic function is -b/3a. Use this formula to find the point of symmetry (x and y axes) of the following function:

ax^3+bx^2+d

Also find the two turning points on this function.

Show that the point of symmetry is the midpoint of the line segment connecting the local maximum and local minimum.

2. Originally Posted by ineedfriendlymathhelp
The formula for findintg the x-coordinate of the point of symmetry of a cubic function is -b/3a. Use this formula to find the point of symmetry (x and y axes) of the following function:

ax^3+bx^2+d

Also find the two turning points on this function.

Show that the point of symmetry is the midpoint of the line segment connecting the local maximum and local minimum.

With a function of degree 3 the point of symmetry is the same as the point of inflection. You'll get the x-coordinate of this point by setting the second derivation equal to zero:

$f(x)=ax^3+bx^2+d~\implies~f''(x)=6ax +3b$

$6ax+2b=0~\implies~x=-\dfrac b{3a}$ and therefore the point of symmetry is $S\left(-\dfrac b{3a} , \dfrac {2b^3}{27a^2} +d\right)$

The condition for a turning point is $f'(x) = 0$

$f'(x) = 3ax^2+2bx$
$3ax^2+2bx=0~\implies~x(3ax+2b)=0~\implies~x=0~\vee ~x=-\dfrac{2b}{3a}$
Therefore $T_1\left(0,d\right)$ and $T_2\left(-\dfrac{2b}{3a}, \dfrac{4b^3}{27a^2}+d \right)$
Now calculate the mean values of the coordinates of $T_1$ and $T_2$ and you'll get the coordinates of point S.


text:
• ### Early-type galaxies at intermediate redshift observed with HST WFC3: perspectives on recent star-formation(1409.6683)

Sept. 23, 2014 astro-ph.GA
We present an analysis of the stellar populations of 102 visually-selected early-type galaxies (ETGs) with spectroscopic redshifts (0.3<z<1.5) from observations in the Early Release Science program with the Wide Field Camera 3 (WFC3) on {\it Hubble Space Telescope} (HST). We fit one- and two-component synthetic stellar models to the ETGs UV-optical-near-IR spectral energy distributions and find a large fraction (~40%) are likely to have experienced a minor (f$\lesssim$10% of stellar mass) burst of recent (t$\lesssim$1 Gyr) star-formation. The measured ages and mass fraction of the young stellar populations do not strongly trend with measurements of galaxy morphology. We note that massive (log(M[$M_{\odot}$])>10.5) recently star-forming ETGs appear to have larger sizes. Furthermore, high-mass, quiescent ETGs identified with likely companions populate a distinct region in the size-mass parameter space, in comparison with the distribution of massive ETGs with evidence of RSF. We conclude that both mechanisms of the quenching of star-formation in disk-like ETGs and (gas-rich, minor) merger activity contribute to the formation of young stars and the size-mass evolution of intermediate redshift ETGs. The number of ETGs for which we have both HST WFC3 panchromatic (especially UV) imaging and spectroscopically-confirmed redshifts is relatively small, therefore a conclusion on the relative roles of both of these mechanisms remains an open question.
• ### UV to IR SEDs of UV selected galaxies in the ELAIS fields: evolution of dust attenuation and star formation activity from z=0.7 to z=0.2(0707.3415)

July 23, 2007 astro-ph
We study the ultraviolet to far-infrared (hereafter UV-to-IR) SEDs of a sample of intermediate redshift (0.2 < z < 0.7) UV-selected galaxies from the ELAIS-N1 and ELAIS-N2 fields by fitting a multi-wavelength dataset to a library of GRASIL templates. Star formation related properties of the galaxies are derived from the library of models by using the Bayesian statistics. We find a decreasing presence of galaxies with low attenuation and low total luminosity as redshift decreases, which does not hold for high total luminosity galaxies. In addition the dust attenuation of low mass galaxies increases as redshift decreases, and this trend seems to disappear for galaxies with M* > 10^11 M_sun. This result is consistent with a mass dependent evolution of the dust to gas ratio, which could be driven by a mass dependent efficiency of star formation in star forming galaxies. The specific star formation rates (SSFR) decrease with increasing stellar mass at all redshifts, and for a given stellar mass the SSFR decreases with decreasing redshift. The differences in the slope of the M*--SSFR relation found between this work and others at similar redshift could be explained by the adopted selection criteria of the samples which, for a UV selected sample, favours blue, star forming galaxies.
• ### Ongoing Formation of Bulges and Black Holes in the Local Universe: New Insights from GALEX(astro-ph/0609436)

Sept. 15, 2006 astro-ph
We analyze a volume-limited sample of massive bulge-dominated galaxies with data from both the Sloan Digital Sky Survey and the Galaxy Evolution Explorer (GALEX) satellite. The galaxies have central velocity dispersions greater than 100 km/s and stellar surface mass densities that lie above the value where galaxies transition from actively star forming to passive systems. The sample is limited to redshifts 0.03<z<0.07. At these distances, the SDSS spectra sample the light from the bulge-dominated central regions of the galaxies. The GALEX NUV data provide high sensitivity to low rates of global star formation in these systems. Our sample of bulge-dominated galaxies exhibits a much larger dispersion in NUV-r colour than in optical g-r colour. Nearly all of the galaxies with bluer NUV-r colours are AGN. Both GALEX images and SDSS colour profiles demonstrate that the excess UV light is associated with an extended disk. We find that galaxies with red outer regions almost never have a young bulge or a strong AGN. Galaxies with blue outer regions have bulges and black holes that span a wide range in age and accretion rate. Galaxies with young bulges and strongly accreting black holes almost always have blue outer disks. Our suggested scenario is one in which the source of gas that builds the bulge and black hole is a low mass reservoir of cold gas in the disk.The presence of this gas is a necessary, but not sufficient condition for bulge and black hole growth. Some mechanism must transport this gas inwards in a time variable way. As the gas in the disk is converted into stars, the galaxies will turn red, but further gas infall can bring them back into the blue NUV-r sequence.(Abridged)
• ### Systematics of the Ultraviolet Rising flux in a GALEX/SDSS sample of Early-type Galaxies(astro-ph/0411356)

Nov. 12, 2004 astro-ph
We present ultraviolet photometry for a sample of morphologically early-type galaxies selected by matching the Sloan Digital Sky Survey Data Release 1 with the GALEX Medium and All-sky Imaging Surveys. We obtain a working sample of 1032 early-type galaxies with GALEX FUV detections, SDSS spectroscopy, and $z<0.2$. Using the SDSS spectra to identify galaxies with even weak star formation or evidence of AGN, and further removing galaxies with any evidence of non early-type morphology, we derive a final sample of 172 red quiescent early-type galaxies. We find that the $FUV-r$ color has a full range of 5 mag. Plotting against the $FUV-r$ color the metallicity sensitive Lick $\rm Mg_2$ and D4000 indices, and the stellar velocity dispersion, we find no correlation between our measurement of UV rising flux, and any parameter sensitive to metallicity.


text:
Absolute intensity on a Kratky camera part 2: partial solutions

There has been some good response to last week’s post, indicating that many of you are or have been in the same bind. Our partial solution might be a bit underwhelming: assume*.

Dr. A. Petzold explains in an e-mail where the problem comes from:

Here I’m in charge for two rather old Kratky cameras currently and we’re expanding with a used SAXSess system. Recently we’ve equipped an old instrument with a Mythen strip detector. During my PhD thesis I’ve had a similar problem as you’ve described in your article.

A multilayer-optics for collimation and monochromatization of the primary beam uses the Bragg principle. Hence not only the wanted Cu-Kalpha radiation is passing the optics but also the 2nd order of twice the energy and the third order of triple the energy and so on. Meaning you have a significant amount of high energy radiation leading to beam hardening as you’ve described.

Our biggest issue with the high energy radiation contamination seems to be that we cannot correctly determine the transmission factor of the materials we measure. While we should have done this before, we need to verify that the transmission factor is the only problem we have.

If we follow the right data corrections procedure (including taking transmission factors into account), we should be able to get a good water scattering pattern after subtraction of the capillary scattering. Cue a 30-minute measurement of capillary followed by the same capillary filled with water (easy if you have a flow-through cell). After this, we can subtract the transmission-factor-corrected water scattering pattern from the empty capillary scattering pattern, by assuming the water absorbs with a factor of 0.391). And behold (in Figure 1)! A nice flat scattering profile that underscores two things:

1. Our capillary is about 1 mm in diameter at the beam position, and
2. The transmission factor is the only issue we have for correct background subtraction.

With this knowledge, we know that by calculating a transmission factor we may get correct data. Since we are usually measuring dilute suspensions in water here, and the capillary is the same for a series of measurements, the assumed transmission factor allows us to continue.

As an added bonus, we see that the background-subtracted water data plateau is at a level of $1 \times 10^{-4}$ (in Anton-Paar Units per Ten Seconds), whereas we know water should scatter at an absolute level of $1.65 \mathrm{ m}^{-1}$. This then gives us a scaling factor for measurements on this instrument with our measurement settings: 16500. multiplying our measurements with this scaling factor scales our other measurements to absolute units too (but mind the assumptions made!).

A check with a few NIST nanoparticle calibration standards shows that we are actually within 10% of their stated concentrations, which is nice. On the down side, when we play around, we notice that we can get an optically flat plateau even when we vary the assumed transmission factor by up to 20%: the accuracy of this assumption is not the best.

At the moment, we are hunting for better ways to determine our transmission factor. In the SAXSess design, Anton Paar has removed the options for installing a moving slit device, and has removed the revolving beamstop found in the older design (which allowed one to quickly move the beamstop in and out). We still have the option of putting a strong scatterer behind our sample, although that has its own issues as well (as discussed before). A separate, movable detector mounted to the lid may be a viable way forward, and if we make this a fast silicon drift detector, it may be possible to ascertain the spectral purity of the radiation at the same time. Time to put on that hat and the eyepatch and hunt for the booty to pay for it. Yarr!

Or one could go for the solutions put forth by Dr. Petzold:

Usually [the high energy filtering is done] by the detector which uses an lower and upper energy threshold. The Mythen unfortunately only has a lower threshold. In order to get an idea of the problem I’d suggest to perform a threshold scan in the Mythen web interface and plotting the counts of one channel against the threshold (see Fig. 4 in [1]). For us using only Ni-filtered Cu radiation we found approx. 20% of the counts originate from high energy radiation from the bremsstrahlung.

So far I know of 2.5 solutions to your problem:
1. Scan with low threshold (e.g. 6.4keV) and directly afterwards with high threshold (e.g. 9keV) and subtract the measurements channel by channel. This leads to a doubling of the measurement time.
2. During SAS2015 I was told by Dectris that you can set up a threshold per channel. So you could also set 6.4keV and 9keV threshold to adjacent channels and subtract there values. This leads to half the resolution of course.
2.5 Using a semitransparent beam stop made of zinc. Zinc has an absorption edge between 8 and 16keV and reduces the intensity of the 8 and 16keV radiation to similar extend.

Knowing the spectral composition of the radiation may also allow us to compensate for the radiation hardening to determine the true transmission factor, although at high absorptions it would become quite imprecise. Thanks to all the helpful tips received from the readers so far. More ideas are always welcome!

1 Comment

1. Comment from Sam Tardif:

“Nice post!
Scanning the threshold sounds good, but how about the change in sensitivity near the channel edges when you change the threshold? Would that impair the quantitative measurement or is it small enough to be negligible?”


text:
Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/555

 Title: Clustered spots in the FitzHugh-Nagumo system Authors: Winter, MWei, J Keywords: Pattern formation; FitzHugh-Nagumo system;Optimal configuration Publication Date: 2005 Publisher: Elsevier Citation: J Differential Equations, 213: 121-145 Abstract: We construct {\bf clustered} spots for the following FitzHugh-Nagumo system: $\left\{\begin{array}{l}\ep^2\Delta u +f(u)-\delta v =0\quad \mbox{in} \ \Om,\\[2mm]\Delta v+ u=0 \quad \mbox{in} \ \Om,\\[2mm] u= v =0 \quad\mbox{on} \ \partial \Om, \end{array} \right.$ where $\Om$ is a smooth and bounded domain in $R^2$. More precisely, we show that for any given integer $K$, there exists an $\ep_{K}>0$ such that for $0<\ep <\ep_K,\, \ep^{m^{'}} \leq \delta \leq \ep^m$ for some positive numbers $m^{'}, m$, there exists a solution $(u_{\ep},v_{\ep})$ to the FitzHugh-Nagumo system with the property that $u_{\ep}$ has $K$ spikes $Q_{1}^\ep, ..., Q_K^\ep$ and the following holds: (i) The center of the cluster $\frac{1}{K} \sum_{i=1}^K Q_i^\ep$ approaches a hotspot point $Q_0\in\Om$. (ii) Set $l^\ep=\min_{i \not = j} |Q_i^\ep -Q_j^\ep| =\frac{1}{\sqrt{a}} \log\left(\frac{1}{\delta \ep^2 }\right) \ep ( 1+o(1))$. Then $(\frac{1}{l^\ep} Q_1^\ep, ..., \frac{1}{l^\ep} Q_K^\ep)$ approaches an optimal configuration of the following problem: {\it $(*) \ \ \$ Given $K$ points $Q_1, ..., Q_K \in R^2$ with minimum distance $1$, find out the optimal configuration that minimizes the functional $\sum_{i \not = j} \log |Q_i-Q_j|$}. URI: http://www.elsevier.com/wps/find/journaldescription.cws_home/622868/description#descriptionhttp://bura.brunel.ac.uk/handle/2438/555 Appears in Collections: MathematicsSchool of Information Systems, Computing and Mathematics Research Papers

Files in This Item:

File Description SizeFormat

 Library (c) Brunel University.    Powered By: DSpace Send us your Feedback. Last Updated: September 14, 2010. Managed by: Hassan Bhuiyan


text:
# Good Apple Hunting

The boys brought him in for questioning, but I didn't think he had anything to do with this. Not really. I just had to know if he knew anything pertinent about that strange passage in the old man's will.

I proceeded to tell him how his old computer science teacher, Professor Lambeau, had been found.

"The victim was strapped securely to a chair in his office. There was a robotic arm on a table across from him that had been retrofitted so that it could shoot a laser out of its index finger. The arm was attached to a computer and the program was coded to rotate the arm slowly up from its initial downward-facing position at a rate of one degree per hour, a la 1960's Batman villains. Eventually, it reached the victim's crotchular region and continued up until the victim was cut cleanly in two.

"We suspect foul play.

"This is his will, and there's a strange section in it which is directed at you, Will. Does this mean anything to you?"

Will, apparently bored, skimmed over the document, probably understanding more of it than any of us did, but when he got to the section addressed to him, he grabbed a notebook and scribbled furiously for about 30 seconds before declaring, "We have to go see about a girl, Detective. She's the killer and I know her name."

He was right, of course, and time to time I reread that passage late at night.

To my former student Will: In the event of my untimely demise, I want you to know that I still remember that conversation we once had:

You ate my apple.
For what possible reason would I eat your apple?
Do you take me for a fool? One would hope not!
I didn't, OK, but let's say I ate your apple. Would you like for me to eat one more? Three more???
Maybe you ate four of them already! Maybe you took my watermelon, too?
Yeah, OK, I ate your watermelon, for your information, but I didn't eat even one of those apples, you old fart!

Now everyone knows that Will is wicked smaat and well known for his love of apples, but I'll never know what that message had to do with the killer's name!

Do you know the killer's name?

Hints:

As mentioned in the comment below, The capital letter "I" is not a "one" because it is pronounced /aɪ/, not /wʌn/.
The "Computer-Science" tag might make you wonder if one of the numerical "clues" is inappropriate; a red herring.
I would hate for the bounty to be unrewarded.
There are 6 (six) parts to this conversational exchange. During each part, Will finds time to secretly take a nibble(sp?) from an apple. The professor notices and uses this to his advantage.
BTW, Nothing Boolean, only the integers.

Another Hint:

Paste's comment, "Assigning each line to a nibble, I came up with 1000 0100 0101 1111 1110 1101." brings us very close.

• Is knowledge of Good Will Hunting necessary to solve this? – Gordon Allocman May 17 '16 at 20:26
• Not at all. The Good Will Hunting stuff is just for fun. The only pertinent information is in the passage directed at Will. – Chowzen May 17 '16 at 20:32
• Is Apple (iPhone & iMac) related to this in any way? – Neon612 May 20 '16 at 13:48
• @VincentAdvocaat You need to read it like you are from South Boston (aka Southy). You can paaaak your caaaaaaa in the yaaaaaad. (You can park your car in the yard). – LeppyR64 May 20 '16 at 14:50
• I wonder if this apple 🍎 and this watermelon 🍉 play any part? – Ken Y-N May 25 '16 at 3:04

Why, her name was

Jenny, of course.

Explanation:

First, what everyone has deduced so far:

So far, we've figured out that each line of the conversation has homophones of powers of 2 in it:
You ate my apple. = 8
For what possible reason would I eat your apple? = 4
Do you take me for a fool? One would hope not! = 4 and 1
I didn't, OK, but let's say I ate your apple. Would you like for me to eat one more? Three more??? = 8, 4, 2, 1
Maybe you ate four of them already! Maybe you took my watermelon, too? = 8, 4, 2
Yeah, OK, I ate your watermelon, for your information, but I didn't eat even one of those apples, you old fart! = 8, 4, 1

Taking each of these lines' numbers and making them into nibbles (4-bit sequences) with 1's for each digit present, we get
8xxx x4xx x4x1 8421 842x 84x1
1000 0100 0101 1111 1110 1101.

Then,

Crunch the nibbles together to get one binary number: 100001000101111111101101. What is that in decimal? It's 8675309, and as any true 80's music aficionado would know, that number belongs to Jenny. Just ask Tommy Tutone.

How do you like them apples?

• That's good work. To think of all the time I wasted trying to break that number down in different ways. A well deserved +1! – Mike M. May 26 '16 at 4:19
• You got a number... of course :) – LeppyR64 May 26 '16 at 4:27
• Just had to read the writing on the wall. – paste May 26 '16 at 5:05
• You got it (you got it) you got it You got the number on the wall – Tonkleton May 26 '16 at 5:11
• Brilliant...simply brilliant! – Adib May 26 '16 at 5:27

Partial just to try and point out the numbers:

You ate my apple.
(ate = 8)

For what possible reason would I eat your apple?
(For = 4)

Do you take me for a fool? One would hope not!
(For = 4, One = 1)

I didn't, OK, but let's say I ate your apple. Would you like for me to eat one more? Three more???
(ate = 8, for = 4, to = 2, one = 1, three = 3 (nope a red herring))

Maybe you ate four of them already! Maybe you took my watermelon, too?
(ate = 8, four = 4, too = 2)

Yeah, OK, I ate your watermelon, for your information, but I didn't eat even one of those apples, you old fart!
(ate = 8, for = 4, one = 1)

Assigning each line to a nibble yields:
Binary: 1000 0100 0101 1111 1110 1101
Decimal: 8 4 5 15 14 13

I'm searching for a 15 character string to use as a key for the substitution. Something to do with WATERMELON or APPLE or OLD FART. (I tried WATERMELONAPPLE and APPLEWATERMELON)

• I think three is the red herring. The rest are all powers of 2, but I haven't been able to come up with any sensible decoding. – Mike M. May 24 '16 at 12:11
• @paste I'm referring to naught, or zero, the integer. OP's statement about Booleans is kind of ambiguous, so it's hard to tell exactly what they meant. How are you interpreting it? – Mike M. May 24 '16 at 13:01
• The powers of two are also in decreasing order within each quip. That might suggest that they encode bits, e.g. 841 is 1101. That would make the code 8, 4, 5, 13, 14, 13. I can't make anything sensible out of it, not even with a shift of three in either direction. – M Oehm May 24 '16 at 16:48
• Assigning each line to a nibble, I came up with 1000 0100 0101 1111 1110 1101. No idea what to do with those though. Assigning them letters just yields gibberish. – paste May 24 '16 at 23:29
• Yep, it's getting frustrating. :-) I've hit all these same things the last couple days, but no real progress. I thought maybe the powers of 2 themselves - 3 2 2 0 3 2 1 0 3 2 1 3 2 0 - might be the encoding, but nothing there yet, either. And one of OP's comments makes me think that's not it. I'm really thinking "apple" has to be some sort of key, but that might be entirely off. – Mike M. May 25 '16 at 2:10

Is it

Yang

Reason:

Took all the numbers in the quote (ate -> 8, for -> 4, etc.) and put them in a sequence which got me 8441413842841. I converted this to ASCII which got me "Niào" which I searched and don't think is a girl's name. Then I decided to remove the lone "2" in the sequence and converted that instead which got me "Yang"

• Can you explain how you converted it to ascii? – LeppyR64 May 18 '16 at 18:18
• I think you're certainly on to something with the numbers. I was working on the same path but hadn't had time to suss it out. – LeppyR64 May 19 '16 at 11:38
• Yeah I'm sure it's something to do with that. There's no cryptography tag so I was hoping it'd be something simple like converting to ASCII. – econoMichael May 19 '16 at 16:37
• You are missing a number in your sequence. – paste May 19 '16 at 16:59
• ...and that's only if you only consider the conversation and not the introduction to it. – paste May 19 '16 at 23:52

Using the binary/numbers, I got 8 - 4 - 5 (For, One) - 15 - 14 - 13.

Based on the letters I got, it seems Mary is the closest (from a list of letters of R-Y-M-A-F-Y-M-W). How I derived the letters was counting from the start using the values provided to and find the letters based on the word.

For example, the 8th word is "reason", so I pulled an "R". And then 4 steps ahead I got "Your", so I pulled "Y", etc.

Another approach is using the numbers to find the letters, which yields:

8th letter, 4th letter, 5th letter, etc....And I get:

8 -> H 4 -> D 5 -> E 15 -> O 14 -> N 13 -> M

Which really made no sense, so I ignored this approach.

• Never knew it would be this much fun "reverse engineering" the proposed answer(s) to my own riddle. +1 to Adib for the effort! – Chowzen May 25 '16 at 1:35


text:
## Second meeting of Week 4

We’ll go back now to Chapter 2, on infinite Ramsey’s theorem, and its connection (via Konig’s tree lemma) to finite Ramsey’s theorem.

Everyone should read Chapter 2, through at least to the middle of page 48. There’s one substantial theorem in this span, namely Theorem 2.1 (although it’s not really too different from Theorem 1.31, finite Ramsey’s theorem, and is in fact a little easier, since one has much less “bookkeeping” to do to make the proof work. Section 2.2 through the middle of page 48 is mostly definitions (of partially ordered sets, tree orders, et cetera.).

Theorem 2.1 is proven by induction, with the base case being the obvious infinite pigeon-hole principle — if infinitely many pigeons arrange themselves among only finitely many pigeon holes, then at least one of the pigeon-holes will end up with infinitely many pigeons. I think it’s much more instructive to start with the base case $$p=2$$. So: Greyson and Joe can present the proof of the following (the case [/latex]p=2[/latex] of Theorem 2.1): if the edges of an infinite complete graph are colored with finitely many colors, then the graph has an infinite complete subgraph all of whose edges have the same color. Then Luca and Sean can present the induction step that completes the proof of Theorem 2.1.

Then we’ll move onto to partial orders (to lay the groundwork for deducing finite results from infinite ones). As I said earlier, everyone should read through all the background on partial orders and tree-orders, and we can discuss and points that are confusing during the live meeting. Bailee and Anthony can first explain what it means for a partial order to be a tree (in the partial order sense), and then present Exercise 2.3 (connecting this concept to trees in the graph-theoretic sense); then Ted and Ryan can present Konig’s lemma (Theorem 2.6).

## Tuesday of week 4 – red group

For Tuesday, everyone should read up through the end of Section 3.1, and do all the exercises. In general when reading mathematics it is a good idea to have paper to hand, to draw pictures and verify claims. This section is one of those situations where it is not a good idea — it is absolutely essential.

At the end of last time, we saw the “AP focussing” argument used to show that for each $$k$$, $$W(k,2)$$ exists, assuming that $$W(k-1,r)$$ exists for every $$r$$. Next, we will move onto to the argument that $$W(3,3)$$ is finite. This requires a new ingredient, because now we need to focus three monochromatic APs of length 2 (all of different colors) on a single, final focal point. Casey can present this.

The argument that $$W(3,3)$$ is finite generalizes to show that $$W(3,r)$$ is finite, for every $$r$$. Ted can present this.

The last special case we’ll consider is $$W(4,3)$$ (requiring focussing three monochromatic APs of length 3, all of different colors, on a single, final focal point). Colin can present this.

We should now be in a position to understand what’s going on in the proof of the general statement, that for each particular choice of $$k$$ and $$r$$, $$W(k,r)$$ is finite (under the inductive hypothesis that $$W(k-1,r’)$$ is finite for every $$r’$$). Bailee can present this.

## Tuesday of Week 4 — blue group

For Tuesday, everyone should read up through the end of Section 3.1, and do all the exercises. In general when reading mathematics it is a good idea to have paper to hand, to draw pictures and verify claims. This section is one of those situations where it is not a good idea — it is absolutely essential.

At the end of last time, we saw the “AP focussing” argument used to show that $$W(3,2)$$ exists. To make sure that we fully understand that argument before moving on, we should start on Tuesday by using the same argument to show that for each $$k$$, $$W(k,2)$$ exists, assuming that $$W(k-1,r)$$ exists for every $$r$$. I’ll  present this (it is very quick — a valid upper bound is easy to justify using the same process that justified $$W(3,2)\leq 5\cdot 65$$. The right picture fully explains the proof).

Next, we will move onto to the argument that $$W(3,3)$$ is finite. This requires a new ingredient, because now we need to focus three monochromatic APs of length 2 (all of different colors) on a single, final focal point. Nick can present this.

The argument that $$W(3,3)$$ is finite generalizes to show that $$W(3,r)$$ is finite, for every $$r$$. Sean can present this.

The last special case we’ll consider is $$W(4,3)$$ (requiring focussing three monochromatic APs of length 3, all of different colors, on a single, final focal point).  Alex can present this.

We should now be in a position to understand what’s going on in the proof of the general statement, that for each particular choice of $$k$$ and $$r$$, $$W(k,r)$$ is finite (under the inductive hypothesis that $$W(k-1,r’)$$ is finite for every $$r’$$). Henry can present this.

## Reading for the second meeting of week three

We’ve now seen Ramsey’s theorem, which concerns finding monochromatic cliques in graphs, and a generalization to hypergraphs ($$p$$-tuples). Now we move on Van der Waerden’s theorem, a somewhat more difficult result concerning finding monochromatic arithmetic progressions in colorings of the natural numbers. This is Chapter 3 of Reimann and Katz; we’ll go back to Chapter 2, on infinite Ramsey’s theorem, later.

The text doesn’t give a complete, formal proof of finite Van der Waerden. Instead, it discusses a few instances of showing the existence of some small finite Van der Waerden numbers, in a way that (hopefully) gives a good intuition for how a full proof should go.

• Everyone should read Chapter 3, through at least to the middle of page 94 (ignore the occasional reference back to Chapter 2).
•  Everyone should think about Exercise 3.2 (construction of a 2-coloring of $${\mathbb N}$$ that fails to have an infinite monochromatic arithmetic progression). Greyson and Joe can tell us about this.
• Here’s another exercise that everyone can think about, and I’ll throw it open to the group to discuss: is there a “soft” way to prove the existence of a 2-coloring of $${\mathbb N}$$ that fails to have an infinite monochromatic arithmetic progression, without actually explicitly exhibiting such a coloring? Hint: how does the number of infinite arithmetic progression compare to the number of natural numbers?
• Ted and Anthony can go over the explanation of why the existence of $$W(k,2)$$ for every $$k$$ implies the existence of  $$W(k,r)$$ for every $$k$$ and $$r$$ (observation 3.1)
• Luca and Ryan can take us through a proof that $$W(3,2)\leq 325$$. (Reimann and Katz go through this quite slowly and discursively; Luca and Ryan, in presenting this bound you can assume that we have all read the long discussion, and so you can be more concise. Start with the hypothesis that $$325$$ works, and go through the four steps outlined on page 93, to verify that hypothesis. Pictures will help!)

## Reading/exercises for Tuesday of Week 3

Note: I won’t have access to my office next week, so I’ll have no blackboard. So when making a presentation you should use some kind of slides — powerpoint or (preferably, since it is optimized for math) Beamer — that you can share on the screen; or use an app that allows you to share a (virtual) blank page that you can write on in a way that everyone can see.

I’ll begin by discussing the state of the art for diagonal Ramsey numbers. Then we will go on to full-blown Ramsey’s theorem. This is Section 1.6; everyone should read this.

• Section 1.6 starts with a treatment of the case of coloring triples with 2 colors. Bailee and Sean can present on this.
• The section continues with an outline of the induction argument that allows us to extend to sets larger than triples (heading “From triples to $$p$$-tuples”), still with two colors.  Casey and Nick can present on this.
• The section ends with a proof for many colors (heading “A different proof”). Colin and Alex can present on this.

Here’s a fun exercise to think about. Use Ramsey’s Theorem (you’ll need to use the more general statement about coloring $$p$$-tuples, rather than the weaker one about coloring pairs) to prove the following statement: for every $$k$$ there is $$N(k)$$ such that however $$N(k)$$ points are put on a plane, with no three in a line, there is some $$k$$ points among the $$N(k)$$ that form the vertices of a convex $$k$$-sided polygon.

## Thursday of week 2, blue group

• Everyone should have a look at Proposition 1.25 (improving the Greenwood and Gleason upper bound on off-diagonal Ramsey numbers by 1, in certain circumstances). We won’t spend much time on this, unless people have questions. It is needed in the proof of Proposition 1.26, so we should at least know the statement and have an idea of its proof.
• Joe will present two arguments for a couple of small exact Ramsey numbers (Proposition 1.26 and 1.27).
• Everyone should read through propositions 1.26 and 1.27, and the discussion afterwards; I’ll make some further comments on this.
• Everyone should think about how a proof for Theorem 1.28 should go; Anthony will tell us about it.
• Ryan will present the proof of Theorem 1.29 (a lower bound for the diagonal Ramsey numbers). Everyone should read this proof, too.

## Friday of week 2, red group

• We’ll start with Greyson presenting the proof of Theorem 1.24 (a binomial coefficient upper bound on the off-diagonal Ramsey numbers).
• Everyone should have a look at Proposition 1.25 (improving the Greenwood and Gleason upper bound on off-diagonal Ramsey numbers by 1, in certain circumstances).
• Luca will present two arguments for a couple of small exact Ramsey numbers (Proposition 1.26 and 1.27); this outlining the proof of Proposition 1.25.
• Everyone should read through propositions 1.26 and 1.27, and the discussion afterwards; I’ll make some further comments on this.
• The book introduces a couple of black boxes. The first is a coloring of a graph on 13 vertices that has neither a red $$K_3$$ nor a blue $$K_5$$ (arrange the 23 vertices in a circle. Use a red edge to join each vertex to its neighbors immediately to the right and immediately to its left, as well as to the vertices 5 to its right and 5 to its left. All other edges are blue). We’ll talk about how to efficiently verify that this coloring does what it claims to do. The second black box is the Paley graph of order 17, which is claimed not to have a red $$K_4$$ nor a blue $$K_4$$. We’ll discuss verifying this, too.
• Everyone should think about how a proof for Theorem 1.28 should go.
• Ted will present the proof of Theorem 1.29 (a lower bound for the diagonal Ramsey numbers). Everyone should read this proof, too.

## Tuesday of week 2, red group

Here’s the plan for Tuesday, June 16, for the Red group:

• Everyone:
* Re-read the proof of Theorem 1.16 — the basic proof strategy will re-appear in later proofs of more expansive Ramsey-type theorems. It will be very helpful to start the proof by taking (with hindsight) $$N=2^{2k}$$; that way, once you have (once) verified that $$\lceil (2^m-1)/2 \rceil = 2^{m-1}$$ for any natural number $$m$$, you get to avoid all the messy algebra at the end of the proof.
* Do exercise 1.18 (which is essentially the Bolzano-Weierstrass theorem for finite sequences).
* Think about the following much harder variant of exercise 1.18: part of that exercise asks you to show that there is a sequence of reals of length $$k^2$$ that has neither an increasing nor a decreasing subsequence of length $$k+1$$. Show that this is best possible, that is, show that every sequence of reals of length $$k^2+1$$ has either an increasing or a decreasing subsequence of length $$k+1$$.
* Study the proof of Theorem 1.19 (Ramsey’s theorem for colouring pairs, with many colors).
* Read Section 1.4, through at least to the proof of Theorem 1.24.
• Individual assignments:
* For both parts of exercise 1.18, and the harder variant, I’ll throw it open to anyone who wants to volunteer ideas.
* Proof of Theorem 1.19 (Ramsey’s theorem about finding a monochromatic $$k$$-clique, when colouring with $$r$$ colours): Bailee.
* Exercise 1.20 (Schur’s theorem, a cute application of Ramsey’s theorem): Casey.
* Theorem 1.23 (another proof of Ramsey’s theorem, that uses “off-diagonal” Ramsey numbers): Colin.
* Theorem 1.24 (getting better upper bounds for Ramsey numbers, using the result of Theorem 1.23): Greyson. (We may not get to this on Tuesday).

## Tuesday of Week 2, Blue group

Here’s the plan for Tuesday, June 16, for the Blue group:

• Everyone:
* Re-read the proof of Theorem 1.16 — the basic proof strategy will re-appear in later proofs of more expansive Ramsey-type theorems. It will be very helpful to start the proof by taking (with hindsight) $$N=2^{2k}$$; that way, once you have (once) verified that $$\lceil (2^m-1)/2 \rceil = 2^{m-1}$$ for any natural number $$m$$, you get to avoid all the messy algebra at the end of the proof.
* Do exercise 1.18 (which is essentially the Bolzano-Weierstrass theorem for finite sequences).
* Think about the following much harder variant of exercise 1.18: part of that exercise asks you to show that there is a sequence of reals of length $$k^2$$ that has neither an increasing nor a decreasing subsequence of length $$k+1$$. Show that this is best possible, that is, show that every sequence of reals of length $$k^2+1$$ has either an increasing or a decreasing subsequence of length $$k+1$$.
* Study the proof of Theorem 1.19 (Ramsey’s theorem for colouring pairs, with many colors).
* Read Section 1.4, through at least to the proof of Theorem 1.24.
• Individual assignments:
* For both parts of exercise 1.18, and the harder variant, I’ll throw it open to anyone who wants to volunteer ideas.
* Proof of Theorem 1.19 (Ramsey’s theorem about finding a monochromatic $$k$$-clique, when colouring with $$r$$ colours): Sean.
* Exercise 1.20 (Schur’s theorem, a cute application of Ramsey’s theorem): Nick.
* Theorem 1.23 (another proof of Ramsey’s theorem, that uses “off-diagonal” Ramsey numbers): Henry.
* Theorem 1.24 (getting better upper bounds for Ramsey numbers, using the result of Theorem 1.23): Alex. (We may not get to this on Tuesday).

## Red group — Friday 9.30 week 1

Here’s the plan for Friday for the Red group:

• Everyone: Read Section 1.3; do exercises 1.14 (easy), 1.18 and 1.20 (both moderate). You could also think about the following much harder variant of exercise 1.18: part of that exercise asks you to show that there is a sequence of reals of length $$k^2$$ that has neither an increasing nor a decreasing subsequence of length $$k+1$$. Show that this is best possible, that is, show that every sequence of reals of length $$k^2+1$$ has either an increasing or a decreasing subsequence of length $$k+1$$.
• Greyson: present exercise 1.8.
• Bailee: present a proof that the complement of a disconnected graph must be connected.
• Ted: present a proof that a graph is bipartite iff it has no odd cycle.
• Casey: present exercise 1.12.
• Colin: present exercise 1.13.
• Luca: present the proof of Theorem 1.16.


text:
# Relative Entropy?

1. Jun 21, 2009

### Fumarium

If I was sitting in my office holding a hot cup of coffee, then suddenly accelerated to close to the speed of light for say 5 minutes of my time, then decelerated to my previous velocity, wouldn't my cup of coffee still be hot? Since only 5 minutes of my time has passed? Even though 60,000 years of my office's time has passed? Doesn't this mean that entropy is relative to velocity? And if the rate of our Universe’s expansion speed is INCREASING - does it correlate then that its entropy is DECREASING?

2. Jun 21, 2009

### The riddler

This doesn't mean that entropy is "decreasing", when you are traveling at close to the speed of light you have increased entropy slower than the universe around. While going at this speed 5 seconds to you could be 60,000 years to your office, meaning that the universe has gone on longer so entropy for the universe has seemed to have gone faster in comparision to you. So your right, entropy is relative to velocity but that is only because velocity is relative to time (through einsteins physics) and time is relative to entropy.

Thus the entropy of the universe is always increasing but the rate inwhich it increases will change with time. For example, right now with all the stars burning the universe is gaining entropy quickly while the universe may be gaining entropy slower in 100 trillion years because the energy and matter in the universe will be more spread out.

3. Jun 21, 2009

### Civilized

Entropy is an observant dependent quantity, just like kinetic energy, etc this does not make the concept meaningless.

No it doesn't, maybe you could describe in detail a particular observer in a particular state of motion and why you think the accelerating expansion of the universe would cause a decrease in entropy? Keep in mind that the accelerating expansion of the universe is very different then accelerating away from your office chair.

4. Jun 21, 2009

Staff Emeritus
None of that follows from the premise.

5. Jun 21, 2009

### lifeson22

Entropy is a measure of the probability of finding a system in a given configuration - period. You might have seen it in your statistical physics or thermodynamics textbooks as:

S$$\propto$$log(g), where the g is the multiplicity of the system's configuration, given by the binomial distribution for a system of N particles of type A or B:

g=$$\frac{N!}{N_{A}!N_{B}!}$$

An isolated system will always progress to a state of highest probability - and thus highest entropy by our definition - because the slightest deviation from equilibrium puts the system in a far less probable configuration.

You're right that something special happens after a hyperspeed trip with your cup of coffee. Moving near the speed of light distorts the space-time continuum, so that five minutes to you is eons to somebody else. If your coffee is not perfectly insulated, heat will dissipate from it and reduce its entropy at the expense of the entropy of its surroundings (which increases) - and this progresses at a rate determined by the gradient of temperature between coffee and surroundings. It's a time dependent process, and because you've been flying at hyperspeeds, the time required for your coffee to cool off will be different from the time measured by somebody sitting in your home planet.

It's not that entropy is velocity-dependent, it's that time is velocity dependent. If you see the process move along a lot faster than a stationary observer, it's because time *IS* moving along very differently for the both of you, not because entropy is taking on different values for both of you.

6. Jun 24, 2009

### Andrew Mason

The cup of coffee would cool in less than five minutes because it would be all over your shirt in the first few seconds. Given the acceleration that would be needed if you were going to do this trip in 5 minutes, local time, you would not feel the scalding hot coffee on your skin because your brain would have exploded from the pressure.

I have a copy of a copy of a book on Relativity and Thermodynamics by Richard Tolman. You can download the chapter on "[URL [Broken] - Relativity-Thermodynamics_Ch_V.pdf"]Relativity and Thermodynamics here[/URL] if you are interested. It is an old book but (relatively) easy to read.

AM:

Last edited by a moderator: May 4, 2017


text:
How to solvethis problem related to redox titration?

A $1.0\ \mathrm{g}$ sample containing $\ce{BaCl2*2H2O}$ was dissolved and an excess of $\ce{K2CrO4}$ solution added. After a suitable period, the $\ce{BaCrO4}$ was filtered, washed and redissolved in $\ce{HCl}$ to convert $\ce{CrO4^2-}$ to $\ce{Cr2O7^2-}$. An excess of $\ce{KI}$ was added, and the liberated iodine was titrated with $84.7\ \mathrm{mL}$ of $0.137\ \mathrm{M}$ sodium thiosulphate. Calculate the percent purity of $\ce{BaCl2*2H2O}$.

I first found the number of mili-equivalents of sodium thiosulphate and equated that to the number of moles of pure $\ce{BaCl2*2H2O}$ times the n-factor i.e. $2$.

From this equation I get the number of moles of pure $\ce{BaCl2*2H2O}$ and then multiply this by its molecular mass to get the mass of pure $\ce{BaCl2*2H2O}$. But it comes greater than $1\ \mathrm{g}$. How to solve this?

Chromium(VI) is reduced to chromium(III) while oxidizing iodide to iodine. So one equivalent of chromate corresponds to 3 equivalents of iodine ($\ce{I}$, not $\ce{I2}$).
$$\ce{BaCl2 \cdot 2 H2O} \equiv \ce{BaCrO4} ~\mathrm{(chrome(VI))} \equiv \frac{3}{2}~\ce{I2} \equiv 3~\ce{S2O3^{2-}}$$
• Your reaction equation is correct. However, spectator ions are not very interesting for understanding what's going on. The essential thing is that 1 mole chromium(IV) oxidizes 3 moles iodide, and 1 mole $\ce{I2}$ will oxidize 2 moles thiosulfate, hence 1 mole iodine atoms oxidize 1 mole thiosulfate. Therefore 3 moles thiosulfate are equivalent to 1 mole chromium(VI) and hence to 1 mole barium chloride. – aventurin Dec 31 '16 at 18:39


text:
# Shopping Tracker

Spring 2019

The questions below are due on Sunday April 07, 2019; 11:59:00 PM.

You are not logged in.

Note that this link will take you to an external site (https://oidc.mit.edu) to authenticate, and then you will be redirected back to this page.

## 1) Overview

In this Design Exercise you'll build a device that could conceivably serve as a mobile objects-in-cart tracker. These are actually starting to appear, but the idea behind it is that as one pushed their grocery/shopping cart around the store and adds stuff, it keeps track of what has been added and displays the current tally. In some sense this serves as a mobile checkout, but the fact that it can be with you is extremely helpful.

We lack the ability to sense particular groceries using barcodes or NFC techniques in our 6.08 kit so instead we'll rely on user input which can take one of several forms:

• Button-based entry (of your choice)
• Button and Tilt based entry (of your construction)
• Speech-based entry (fun, but hard)

The user should be able to specify the quantity of each grocery item added. The system will communicate with a server-side script including a database of your design and construction that keeps track of the current shopping tally for the user.

The user should be able to add an arbitrary number of an item to their list, including handling duplicate item additions (you realize you actually need one dozen more eggs than you already put in your cart)

Upon each POSTing of a new item, the server should respond with a tally of all items so far and price total for the cart.

For demonstration purposes, at least 12 grocery items with distinct prices must exist within the system.

The user should be able to check-out/reset the system.

Any questions on the spec, of course always feel free to post on Piazza.

Any late factors are based on the timestamp for the last time that the URL is entered on the page or when the code is uploaded or when a comment is added/changed. If you change your URL after the deadline you will incur a late penalty. If you upload code after the deadline, you will incur a late penalty. If you comment after the deadline, you will incur a late penalty. One-Week Extensions DO NOT APPLY Design Exercises.

Problem Status:
A Python Error Occurred:

Error on line 2 of python tag (line 45 of file /S19/ex08/shopping_sorter):

Enter the url for the video

SUBMIT ALL YOUR CODE AS A ZIP FILE BELOW (DOUBLE CHECK THAT YOU HAVE ZIPPED IT CORRECTLY). YOU WILL LOSE POINTS IF ALL FILES ARE NOT PRESENT!

No file selected

Enter any comments you may want us to know about. For example, if you started this exercise but don't want it graded, make a note here. Please hit submit on this question even if you don't have any comments.

Back to Exercise 08

This page was last updated on Sunday April 14, 2019 at 09:53:55 AM (revision 7d1f645).


text:
Copied to
clipboard

## G = C23×C4○D4order 128 = 27

### Direct product of C23 and C4○D4

direct product, p-group, metabelian, nilpotent (class 2), monomial

Aliases: C23×C4○D4, D43C24, C2.3C26, Q83C24, C4.23C25, C22.1C25, C25.97C22, C23.282C24, C24.661C23, D4(C23×C4), C4(D4×C23), C4(Q8×C23), Q8(C23×C4), (C2×C4)⋊5C24, (C24×C4)⋊11C2, (D4×C23)⋊20C2, (C2×D4)⋊25C23, (C2×Q8)⋊26C23, (Q8×C23)⋊16C2, (C23×C4)⋊61C22, (C22×C4)⋊26C23, (C22×D4)⋊68C22, (C22×Q8)⋊73C22, C4(C22×C4○D4), (C2×Q8)(C23×C4), (C2×C4)(Q8×C23), (C2×C4)2(C22×D4), (C22×C4)2(C2×D4), (C22×C4)2(C2×Q8), (C2×C4)2(C22×Q8), (C22×C4)(C4○D4), (C23×C4)(Q8×C23), (C22×C4)(Q8×C23), (C23×C4)(C22×Q8), (C22×C4)2(C22×Q8), (C2×C4)2(C2×C4○D4), (C2×C4)(C22×C4○D4), (C22×C4)(C2×C4○D4), (C22×C4)(C22×C4○D4), SmallGroup(128,2322)

Series: Derived Chief Lower central Upper central Jennings

 Derived series C1 — C2 — C23×C4○D4
 Chief series C1 — C2 — C22 — C23 — C24 — C23×C4 — C24×C4 — C23×C4○D4
 Lower central C1 — C2 — C23×C4○D4
 Upper central C1 — C23×C4 — C23×C4○D4
 Jennings C1 — C2 — C23×C4○D4

Generators and relations for C23×C4○D4
G = < a,b,c,d,e,f | a2=b2=c2=d4=f2=1, e2=d2, ab=ba, ac=ca, ad=da, ae=ea, af=fa, bc=cb, bd=db, be=eb, bf=fb, cd=dc, ce=ec, cf=fc, de=ed, df=fd, fef=d2e >

Subgroups: 3644 in 3260 conjugacy classes, 2876 normal (6 characteristic)
C1, C2, C2, C2, C4, C22, C22, C2×C4, D4, Q8, C23, C23, C22×C4, C2×D4, C2×Q8, C4○D4, C24, C24, C24, C23×C4, C23×C4, C22×D4, C22×Q8, C2×C4○D4, C25, C24×C4, D4×C23, Q8×C23, C22×C4○D4, C23×C4○D4
Quotients: C1, C2, C22, C23, C4○D4, C24, C2×C4○D4, C25, C22×C4○D4, C26, C23×C4○D4

Smallest permutation representation of C23×C4○D4
On 64 points
Generators in S64
(1 5)(2 6)(3 7)(4 8)(9 23)(10 24)(11 21)(12 22)(13 32)(14 29)(15 30)(16 31)(17 41)(18 42)(19 43)(20 44)(25 55)(26 56)(27 53)(28 54)(33 64)(34 61)(35 62)(36 63)(37 45)(38 46)(39 47)(40 48)(49 60)(50 57)(51 58)(52 59)
(1 11)(2 12)(3 9)(4 10)(5 21)(6 22)(7 23)(8 24)(13 20)(14 17)(15 18)(16 19)(25 63)(26 64)(27 61)(28 62)(29 41)(30 42)(31 43)(32 44)(33 56)(34 53)(35 54)(36 55)(37 57)(38 58)(39 59)(40 60)(45 50)(46 51)(47 52)(48 49)
(1 31)(2 32)(3 29)(4 30)(5 16)(6 13)(7 14)(8 15)(9 41)(10 42)(11 43)(12 44)(17 23)(18 24)(19 21)(20 22)(25 50)(26 51)(27 52)(28 49)(33 38)(34 39)(35 40)(36 37)(45 63)(46 64)(47 61)(48 62)(53 59)(54 60)(55 57)(56 58)
(1 2 3 4)(5 6 7 8)(9 10 11 12)(13 14 15 16)(17 18 19 20)(21 22 23 24)(25 26 27 28)(29 30 31 32)(33 34 35 36)(37 38 39 40)(41 42 43 44)(45 46 47 48)(49 50 51 52)(53 54 55 56)(57 58 59 60)(61 62 63 64)
(1 37 3 39)(2 38 4 40)(5 45 7 47)(6 46 8 48)(9 59 11 57)(10 60 12 58)(13 64 15 62)(14 61 16 63)(17 27 19 25)(18 28 20 26)(21 50 23 52)(22 51 24 49)(29 34 31 36)(30 35 32 33)(41 53 43 55)(42 54 44 56)
(1 53)(2 54)(3 55)(4 56)(5 27)(6 28)(7 25)(8 26)(9 36)(10 33)(11 34)(12 35)(13 49)(14 50)(15 51)(16 52)(17 45)(18 46)(19 47)(20 48)(21 61)(22 62)(23 63)(24 64)(29 57)(30 58)(31 59)(32 60)(37 41)(38 42)(39 43)(40 44)

G:=sub<Sym(64)| (1,5)(2,6)(3,7)(4,8)(9,23)(10,24)(11,21)(12,22)(13,32)(14,29)(15,30)(16,31)(17,41)(18,42)(19,43)(20,44)(25,55)(26,56)(27,53)(28,54)(33,64)(34,61)(35,62)(36,63)(37,45)(38,46)(39,47)(40,48)(49,60)(50,57)(51,58)(52,59), (1,11)(2,12)(3,9)(4,10)(5,21)(6,22)(7,23)(8,24)(13,20)(14,17)(15,18)(16,19)(25,63)(26,64)(27,61)(28,62)(29,41)(30,42)(31,43)(32,44)(33,56)(34,53)(35,54)(36,55)(37,57)(38,58)(39,59)(40,60)(45,50)(46,51)(47,52)(48,49), (1,31)(2,32)(3,29)(4,30)(5,16)(6,13)(7,14)(8,15)(9,41)(10,42)(11,43)(12,44)(17,23)(18,24)(19,21)(20,22)(25,50)(26,51)(27,52)(28,49)(33,38)(34,39)(35,40)(36,37)(45,63)(46,64)(47,61)(48,62)(53,59)(54,60)(55,57)(56,58), (1,2,3,4)(5,6,7,8)(9,10,11,12)(13,14,15,16)(17,18,19,20)(21,22,23,24)(25,26,27,28)(29,30,31,32)(33,34,35,36)(37,38,39,40)(41,42,43,44)(45,46,47,48)(49,50,51,52)(53,54,55,56)(57,58,59,60)(61,62,63,64), (1,37,3,39)(2,38,4,40)(5,45,7,47)(6,46,8,48)(9,59,11,57)(10,60,12,58)(13,64,15,62)(14,61,16,63)(17,27,19,25)(18,28,20,26)(21,50,23,52)(22,51,24,49)(29,34,31,36)(30,35,32,33)(41,53,43,55)(42,54,44,56), (1,53)(2,54)(3,55)(4,56)(5,27)(6,28)(7,25)(8,26)(9,36)(10,33)(11,34)(12,35)(13,49)(14,50)(15,51)(16,52)(17,45)(18,46)(19,47)(20,48)(21,61)(22,62)(23,63)(24,64)(29,57)(30,58)(31,59)(32,60)(37,41)(38,42)(39,43)(40,44)>;

G:=Group( (1,5)(2,6)(3,7)(4,8)(9,23)(10,24)(11,21)(12,22)(13,32)(14,29)(15,30)(16,31)(17,41)(18,42)(19,43)(20,44)(25,55)(26,56)(27,53)(28,54)(33,64)(34,61)(35,62)(36,63)(37,45)(38,46)(39,47)(40,48)(49,60)(50,57)(51,58)(52,59), (1,11)(2,12)(3,9)(4,10)(5,21)(6,22)(7,23)(8,24)(13,20)(14,17)(15,18)(16,19)(25,63)(26,64)(27,61)(28,62)(29,41)(30,42)(31,43)(32,44)(33,56)(34,53)(35,54)(36,55)(37,57)(38,58)(39,59)(40,60)(45,50)(46,51)(47,52)(48,49), (1,31)(2,32)(3,29)(4,30)(5,16)(6,13)(7,14)(8,15)(9,41)(10,42)(11,43)(12,44)(17,23)(18,24)(19,21)(20,22)(25,50)(26,51)(27,52)(28,49)(33,38)(34,39)(35,40)(36,37)(45,63)(46,64)(47,61)(48,62)(53,59)(54,60)(55,57)(56,58), (1,2,3,4)(5,6,7,8)(9,10,11,12)(13,14,15,16)(17,18,19,20)(21,22,23,24)(25,26,27,28)(29,30,31,32)(33,34,35,36)(37,38,39,40)(41,42,43,44)(45,46,47,48)(49,50,51,52)(53,54,55,56)(57,58,59,60)(61,62,63,64), (1,37,3,39)(2,38,4,40)(5,45,7,47)(6,46,8,48)(9,59,11,57)(10,60,12,58)(13,64,15,62)(14,61,16,63)(17,27,19,25)(18,28,20,26)(21,50,23,52)(22,51,24,49)(29,34,31,36)(30,35,32,33)(41,53,43,55)(42,54,44,56), (1,53)(2,54)(3,55)(4,56)(5,27)(6,28)(7,25)(8,26)(9,36)(10,33)(11,34)(12,35)(13,49)(14,50)(15,51)(16,52)(17,45)(18,46)(19,47)(20,48)(21,61)(22,62)(23,63)(24,64)(29,57)(30,58)(31,59)(32,60)(37,41)(38,42)(39,43)(40,44) );

G=PermutationGroup([[(1,5),(2,6),(3,7),(4,8),(9,23),(10,24),(11,21),(12,22),(13,32),(14,29),(15,30),(16,31),(17,41),(18,42),(19,43),(20,44),(25,55),(26,56),(27,53),(28,54),(33,64),(34,61),(35,62),(36,63),(37,45),(38,46),(39,47),(40,48),(49,60),(50,57),(51,58),(52,59)], [(1,11),(2,12),(3,9),(4,10),(5,21),(6,22),(7,23),(8,24),(13,20),(14,17),(15,18),(16,19),(25,63),(26,64),(27,61),(28,62),(29,41),(30,42),(31,43),(32,44),(33,56),(34,53),(35,54),(36,55),(37,57),(38,58),(39,59),(40,60),(45,50),(46,51),(47,52),(48,49)], [(1,31),(2,32),(3,29),(4,30),(5,16),(6,13),(7,14),(8,15),(9,41),(10,42),(11,43),(12,44),(17,23),(18,24),(19,21),(20,22),(25,50),(26,51),(27,52),(28,49),(33,38),(34,39),(35,40),(36,37),(45,63),(46,64),(47,61),(48,62),(53,59),(54,60),(55,57),(56,58)], [(1,2,3,4),(5,6,7,8),(9,10,11,12),(13,14,15,16),(17,18,19,20),(21,22,23,24),(25,26,27,28),(29,30,31,32),(33,34,35,36),(37,38,39,40),(41,42,43,44),(45,46,47,48),(49,50,51,52),(53,54,55,56),(57,58,59,60),(61,62,63,64)], [(1,37,3,39),(2,38,4,40),(5,45,7,47),(6,46,8,48),(9,59,11,57),(10,60,12,58),(13,64,15,62),(14,61,16,63),(17,27,19,25),(18,28,20,26),(21,50,23,52),(22,51,24,49),(29,34,31,36),(30,35,32,33),(41,53,43,55),(42,54,44,56)], [(1,53),(2,54),(3,55),(4,56),(5,27),(6,28),(7,25),(8,26),(9,36),(10,33),(11,34),(12,35),(13,49),(14,50),(15,51),(16,52),(17,45),(18,46),(19,47),(20,48),(21,61),(22,62),(23,63),(24,64),(29,57),(30,58),(31,59),(32,60),(37,41),(38,42),(39,43),(40,44)]])

80 conjugacy classes

 class 1 2A ··· 2O 2P ··· 2AM 4A ··· 4P 4Q ··· 4AN order 1 2 ··· 2 2 ··· 2 4 ··· 4 4 ··· 4 size 1 1 ··· 1 2 ··· 2 1 ··· 1 2 ··· 2

80 irreducible representations

 dim 1 1 1 1 1 2 type + + + + + image C1 C2 C2 C2 C2 C4○D4 kernel C23×C4○D4 C24×C4 D4×C23 Q8×C23 C22×C4○D4 C23 # reps 1 3 3 1 56 16

Matrix representation of C23×C4○D4 in GL5(𝔽5)

 4 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 4 0 0 0 0 0 4
,
 4 0 0 0 0 0 4 0 0 0 0 0 4 0 0 0 0 0 4 0 0 0 0 0 4
,
 4 0 0 0 0 0 1 0 0 0 0 0 4 0 0 0 0 0 4 0 0 0 0 0 4
,
 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 2
,
 1 0 0 0 0 0 4 0 0 0 0 0 4 0 0 0 0 0 0 1 0 0 0 4 0
,
 4 0 0 0 0 0 4 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0

G:=sub<GL(5,GF(5))| [4,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,4,0,0,0,0,0,4],[4,0,0,0,0,0,4,0,0,0,0,0,4,0,0,0,0,0,4,0,0,0,0,0,4],[4,0,0,0,0,0,1,0,0,0,0,0,4,0,0,0,0,0,4,0,0,0,0,0,4],[1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,2,0,0,0,0,0,2],[1,0,0,0,0,0,4,0,0,0,0,0,4,0,0,0,0,0,0,4,0,0,0,1,0],[4,0,0,0,0,0,4,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0] >;

C23×C4○D4 in GAP, Magma, Sage, TeX

C_2^3\times C_4\circ D_4
% in TeX

G:=Group("C2^3xC4oD4");
// GroupNames label

G:=SmallGroup(128,2322);
// by ID

G=gap.SmallGroup(128,2322);
# by ID

G:=PCGroup([7,-2,2,2,2,2,2,-2,925,352]);
// Polycyclic

G:=Group<a,b,c,d,e,f|a^2=b^2=c^2=d^4=f^2=1,e^2=d^2,a*b=b*a,a*c=c*a,a*d=d*a,a*e=e*a,a*f=f*a,b*c=c*b,b*d=d*b,b*e=e*b,b*f=f*b,c*d=d*c,c*e=e*c,c*f=f*c,d*e=e*d,d*f=f*d,f*e*f=d^2*e>;
// generators/relations

׿
×
𝔽


text:
# Conformal map from unit disk to polygon

(Stein, Complex analysis, p.253) If $$F(z)= \int_1^z \frac{d\zeta}{(1-\zeta ^n)^{2/n}}$$ then $F$ maps the unit disk conformally onto the interior of a regular polygon with $n$ sides and perimeter $$2^{\frac{n-2}{n}}\int_0^\pi(\sin\theta)^{-2/n}d\theta$$

I know about conformal maps from $\Bbb{H}$(upper half plane) to polygon given by Schwarz-Christoffel integral. So I tried to consider $F \circ G$ where $G: \Bbb H \to \Bbb D$ by $G(z)=\frac{i-z}{i+z}$. But change of variables does not make the integrand simple. $\zeta = G(w), d\zeta = -2idw/(i+w)^2$ so $d\zeta/(1-\zeta ^n)^{2/n}=cdw/((i+w)^n-(i-w)^n)^{2/n}$. So I cannot use Schwarz-Christoffel integral. What should I do? I tried also $\zeta=e^{i\theta}$ but don't know how to proceed.

The form of the derivative $\dfrac{d\zeta}{(1-\zeta ^n)^{2/n}}$ tells us that the map will create $n$ interior angles of size $\pi(1-2/n)$, which is exactly the interior angle of a regular $n$-gone. Of course, angles do not determine an $n$-gon for $n>3$. But we can also observe the symmetry. For this, it helps to change the lower limit of integration to $0$ (I don't understand why it's set at $1$ to begin with; in any case this only contributes a constant): $$\begin{split}F(e^{2\pi i/n }z) &= \int_0^{e^{2\pi i/n }z} \frac{d\zeta}{(1-\zeta ^n)^{2/n}} \\ & =\int_0^{z} \frac{e^{2\pi i/n }\,d\zeta}{(1-(e^{2\pi i/n }\zeta) ^n)^{2/n}} \\ & = e^{2\pi i/n } \int_0^{z} \frac{d\zeta}{(1-\zeta^n)^{2/n}} \\ & = e^{2\pi i/n } F(z)\end{split}$$ where the second step is a change of variable.
Thus, the image of $F$ has $n$-fold symmetry, which proves it is a regular $n$-gon.
Finally, the perimeter is computed by plugging $\zeta=e^{i\theta}$ into $$\int_{|\zeta|=1}\dfrac{d\zeta}{|1-\zeta^n|^{2/n}}$$ and simplifying a bit. Note that $|1-\zeta^n|^2=2-2\cos n\theta = 4\sin^2(n\theta/2)$ and use periodicity.


text:
# Circular Array Rotation

My code works fine, but it's takes too much time, say around 65 seconds, for large input data. If there are 50,000 numbers in the list $a$ and we have to rotate the numbers 45,000 times then it takes 1 minute.

How can I reduce the time it takes to print all the numbers?

Problem: perform an operation called a right circular rotation on an array of integers [a0 , a1 , a2 , ..a(n-1)]. After performing one right circular rotation operation, the array is transformed to [a(n-1) , a0 , a1 ,..a(n-2)].

Input Format

• The first line contains 3 space-separated integers, $n$, $k$ and $q$ respectively.
• The second line contains $n$ space-separated integers, where each integer $i$ describes array element a[i] (where $0 \le i<n$).
• Each of the $q$ subsequent lines contains a single integer denoting $m$.
n,k,q = input().strip().split(' ') #n=no of integers in the list , k=no of rotation ,q=no of lines for integer m

n,k,q = [int(n),int(k),int(q)]
a = [int(a_temp) for a_temp in input().strip().split(' ')]

for i in range(0,k):
a=[a.pop(n-1)]+a  #for putting the last element to the first position and del it from the last pos

for a0 in range(q):    # printing value of a at a given index
m = int(input().strip())
print(a[m])

Sample Input

3 2 3
1 2 3
0
1
2

Sample Output

2
3
1

Explanation

• After the first rotation, the array becomes [3, 1, 2].
• After the second (and final) rotation, the array becomes [2, 3, 1].
• Let's refer to the array's final state as array $b$. For each query, we just have to print the value of b[m] on a new line:
• $m=0$, so we print $2$ on a new line.
• $m=1$, so we print $3$ on a new line.
• $m=2$, so we print $1$ on a new line.

1. You can change your array packing to use map instead.

n, k, q = map(int, input().strip().split(' '))

2. When popping the last element you don't need to pass an argument.

3. Rather than popping each element, you can perform two slices and an addition. You would also have to use the modulo operator, %, for when $k \ge n$.

k %= n
a = a[-k:] + a[:-k]

4. You don't need to strip a number, as int will do this for you.

This can get you:

n, k, q = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
a = a[-k:] + a[:-k]
for _ in range(q):
print(a[int(input()])

If you however want some sugar you can use collections.deque, it comes with deque.rotate that can perform the rotation in (3) for you. which can result in:

from collections import deque

n, k, q = map(int, input().strip().split(' '))
a = deque(map(int, input().strip().split(' ')))
a.rotate(k)
for _ in range(q):
print(a[int(input()])

The above is good enough for the hackerrank challenge, however performs worse than the code above it. Rotating the array is $O(n)$, where the deque is $O(k)$. But indexing the array is $O(1)$, where the deque is $O(n)$. This means the first code block is $O(n + q)$ and the second is $O(k + nq)$. To make the second $O(n + q)$ all you need to do is change it to an array before the for loop, via list.

whenever you profile code, you should always take more than one timing, with more than one input. Hai Vu done neither of these. Using my wrapper to timeit, I wrote some code to profile; deque (Peilonrayz), adding slices (mkrieger), and deleting a slice (Hai Vu), as these are the fastest functions. However to keep things unbiased I've made a couple of adjustments:

• All code will be a Python function in __main__.
• All functions work correctly with any $k$ and when $n \ne 0$. (I use % to do this.)
• I run each function 10000 times per timeit.
• I run each timeit 10 times, and take the average and interquartile range.

This should give each and every function call the same amount of overhead. Here is the code that I use to time the functions.

from collections import deque

from graphtimer import time, GraphTimer, flat, time
import matplotlib.pyplot as plt

def mkrieger(a, k):
k %= len(a)
return a[-k:] + a[:-k]

def peilonrayz(a, k):
a = deque(a)
a.rotate(k)
return a

def hai_vu(a, k):
k %= len(a)
b = a[-k:]
del a[-k:]
a[0:0] = b

class Timer(GraphTimer):
functions = [
'mkrieger',
'peilonrayz',
'hai_vu',
]
inputs = [
'a = list(range(100)); k = {}'
]
domain = range(1, 101, 1)
titles = [
'100'
]

if __name__ == '__main__':
fig, axs = plt.subplots(nrows=1, ncols=1, sharex=True)
Timer(amount=10, number=10000, stmt='fn(a, k)').plot_axes(flat(axs), show_titles=True)
plt.show()

Which outputs:

• k=k % len(a) should also be there ,in case no of rotation exceeds the length of the list a. – Pygirl Jan 8 '17 at 13:41
• @KritiSahu Yeah that's right, I didn't check for out of bound data. Just makes me want to use deque even more, ;P – Peilonrayz Jan 8 '17 at 13:55
• but can i import this python module in spoj idle or in hackkerrank? – Pygirl Jan 8 '17 at 13:58
• @KritiSahu I don't know about spoj, but it wouldn't be a good IDLE if you couldn't. As for hackkerrank, I did, and it got me +20. – Peilonrayz Jan 8 '17 at 14:01
• @KritiSahu You can import all the modules in the (3.6) stdlib, except secrets, turtle, tkinter, tkinter.ttk, tkinter.tix, tkinter.scrolledtext, typing, ensurepip, zipapp, msilib, msvcrt, winreg, and winsound. – Peilonrayz Jan 8 '17 at 15:01

Instead of rotating the list $k$ times by one position, rotate it by $k$ positions in a single step.

In Python, this can be done by simple slice operations:

def rotate(a, k):
"""Rotate a by k positions to the right.

>>> rotate([1, 2, 3], 1)
[3, 1, 2]
>>> rotate([0, 1, 2, 3, 4], -2)
[2, 3, 4, 0, 1]
"""
r = k % len(a)
return a[-r:] + a[:-r]

• a[-r:] are the last r items of a.
• a[:-r] are all but the last r items of a.

Note that by taking $k$ modulo the length of a, values of $k$ outside the range $0, \dots, n-1$ will also work.

My first attempt is to do a loop k times, each time rotate one element of the list in place:

for _ in range(k):
a.insert(0, a.pop()]

This turns out to be slightly better than the original poster (OP) Kriti Sahu's solution (we will see timing numbers later). However, my solution was far worse than other answers here.

Next up, I moved the last k elements to the beginning of the list in place (none of my solution creates a new array, all done in place--the key to performance):

b = a[-k:]  # Save off the last k elements
del a[-k:]  # Delete the last k elements
a[0:0] = b  # Insert to the front

This turns out to be the best timing so far. Here is a little script I wrote to compare solutions I see so far:

import timeit

def time_and_report(expression, setup, header):
print '{}: {}'.format(header, expression)
timing = timeit.timeit(stmt=expression, setup=setup)
print '{} second(s)\n'.format(timing)

#
# Setup
#
array_size = 100
number_of_rotations = 10
setup = 'a=range({array_size}); k={number_of_rotations}'.format(**locals())
deque_setup = 'from collections import deque;' + setup
mkrieger1_setup = """
def rotate(a, k):
r = k % len(a);
return a[-r:] + a[:-r]
""" + setup

#
# Compare timings
#
time_and_report('for _ in range(k): a.insert(0, a.pop())', setup, 'Hai 1')
time_and_report('b = a[-k:]; del a[-k:]; a[0:0] = b', setup, 'Hai 2')
time_and_report('a = a[-k:] + a[:-k]', setup, 'Peilonrayz 1')
time_and_report('a = deque(a); a.rotate(k)', deque_setup, 'Peilonrayz 2')
time_and_report('a = rotate(a, k)', mkrieger1_setup, 'mkrieger1')
time_and_report('a = [a[(i+k) % len(a)] for i in range(0, len(a))]', setup, 'Andi Kleve')
time_and_report('for _ in range(k): a=[a.pop()]+a', setup, 'Original')

And here is the output of my timing tests for array of 100 elements:

Hai 1: for _ in range(k): a.insert(0, a.pop())
6.80668497086 second(s)

Hai 2: b = a[-k:]; del a[-k:]; a[0:0] = b
0.700757980347 second(s)

Peilonrayz 1: a = a[-k:] + a[:-k]
1.20484399796 second(s)

Peilonrayz 2: a = deque(a); a.rotate(k)
1.6975209713 second(s)

mkrieger1: a = rotate(a, k)
1.62001395226 second(s)

Andi Kleve: a = [a[(i+k) % len(a)] for i in range(0, len(a))]
39.2207920551 second(s)

Original: for _ in range(k): a=[a.pop()]+a
8.81602191925 second(s)

# A Few Notes

• The deque solution turns out to be worse than the list solution because the overhead of turning a list into a deque
• When performance is important, operate the list in place will be faster than creating a new list
• Andi Kleve's solution it much worse than that of the OP
• I have a couple of problems with how you timed your code. And so I updated my answer with what I think is a fair, unbiased, timing of the top three functions. – Peilonrayz Jan 9 '17 at 10:42

Don't rotate the array by copying - that is costly. Simply modify how you access the elements: the result of the N-th rotation can be output as follows (here N=2 as example):

a = range(0,5)
N = 2
[a[(i+N) % len(a)] for i in range(0, len(a))]

• This is incorrect: by rotating 2 times, I expect [3, 4, 0, 1, 2], but got [2, 3, 4, 0, 1] -- it seems you are rotating the wrong direction. Also, see my post for your timing. – Hai Vu Jan 8 '17 at 18:00
• @HaiVu I don't think that's fair, the point as I understand it is that you avoid creating the rotated array explicitly (which is just shown as an example) but instead index into it as shown. So this should be compared such that the other methods also step through the entire array again. – harold Jan 9 '17 at 3:05

Put the elements in the shifted position directly removing the need to shift completely:

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
int n;
int k;
int q;
scanf("%d %d %d",&n,&k,&q);
int *a = malloc(sizeof(int) * n);
for(int a_i = 0; a_i < n; a_i++){

int la=floor((k+a_i)/n);

int j=a_i+k-la*n;
scanf("%d",&a[j]);
}
for(int a0 = 0; a0 < q; a0++){
int m;
scanf("%d",&m);
printf("%d\n",a[m]);
}
return 0;
}

• Welcome to Code Review Mohamed. I don't believe translating this into C was what the OP wanted or the site is intended to do. – chicks Jan 9 '17 at 2:56
• @chicks yeah sorry i dont know python actually im still learning it ... but i just wanted to transmit the idea in some way ... i think this can perform better what do you think? – Mohamed Osman Jan 9 '17 at 3:16
• @chicks instead of performing any shift operation on the array just inputting it into the desired position from the start .... any feedback? – Mohamed Osman Jan 9 '17 at 3:19
• You can always ask a new question here to get feedback. Maybe mention that you were inspired by this question and link to it. – Graipher Jan 9 '17 at 7:19