text:
fabricatr is a package designed to help you imagine your data before you collect it. While many solutions exist for creating simulated datasets, fabricatr is specifically designed to make the creation of realistic social science datasets easy. In particular, we need to be able to imagine correlated data and heirarchical data.

fabricatr is a member of the DeclareDesign software suite that includes the r packages randomizr, estimatr, and Declare Design. fabricatr plays well with the tidyverse.

# Basics

The workhorse function is fabricate. You provide a number to N, then a series of named functions. A nice feature is that you can use N as an argument to any of the functions you supply. Later functions can depend on values defined earlier, making the creation of correlated data easy

library(fabricatr)
my_data <- fabricate(N = 5, Y = runif(N), Y2 = Y*5)
my_data
##   ID          Y        Y2
## 1  1 0.41562700 2.0781350
## 2  2 0.24783623 1.2391812
## 3  3 0.26713051 1.3356526
## 4  4 0.74410844 3.7205422
## 5  5 0.06653615 0.3326807

# Hierarchical data

We can create hierarchical data through use of the level function. In the example below, we create 2 cities, each with an elevation. We then create 3 citizens per city, each with an income.

1. The meaning of N changes. In the cities line, N means 2, the number of cities. In the citizens line, N means 3, the number of citizens.
2. The data created at the cities level is constant within cities. Each city has its own elevation. The data created at the citizens level is not constant within cities.
3. Variables created at a lower level can depend on variables created at a higher level. Citizen’s income depends on the elevation of cities.
my_data <-
fabricate(
cities = level(N = 2, elevation = runif(n = N, min = 1000, max = 2000)),
citizens = level(N = 3, income = round(elevation * rnorm(n = N, mean = 5)))
)
my_data
##   cities elevation citizens income
## 1      1  1112.361        1   4874
## 2      1  1112.361        2   4609
## 3      1  1112.361        3   4354
## 4      2  1736.349        4   8673
## 5      2  1736.349        5   5764
## 6      2  1736.349        6  10800

# Bringing in your own data

An essential part of imagining your data before you collect it is the ability to build on the data you all ready have.

A second way you may wish to use existing data is bootstrap a new dataset from it, thereby preserving all the natural inter-correlations.

## Modifying existing data

If you have already conducted a baseline survey, you may which to imagine how the endline may deviate from it. In this case, you will want to add new variables to your existing dataset. Notice that the meaning of N in the definition of Y_post automatically refers to the number of rows in the dataset provided to the data argument.

baseline_survey <- fabricate(N = 5, Y_pre = rnorm(N))

my_endline <- fabricate(data = baseline_survey,
Y_post = Y_pre + rnorm(N))
my_endline
##   ID      Y_pre      Y_post
## 1  1 -1.1493787 -1.85048959
## 2  2  0.2465355  1.30343303
## 3  3  0.2900489  0.18682424
## 4  4 -0.5520475  0.09666843
## 5  5  0.3632573  2.53695339

## Bootstrapping

Suppose you wanted to bootstrap from your baseline survey.

bootsrapped_data <- resample_data(baseline_survey, N = 10)
bootsrapped_data
##    ID      Y_pre
## 1   1 -1.1493787
## 2   1 -1.1493787
## 3   2  0.2465355
## 4   3  0.2900489
## 5   2  0.2465355
## 6   2  0.2465355
## 7   1 -1.1493787
## 8   5  0.3632573
## 9   1 -1.1493787
## 10  3  0.2900489

The real utility of this function comes when bootstrapping from hierarchical data. The example below takes a dataset that contains 2 cities, each with 3 citizens, then bootstraps to 3 cities, each with 5 citizens.

my_data <-
fabricate(
cities = level(N = 2, elevation = runif(n = N, min = 1000, max = 2000)),
citizens = level(N = 3, income = round(elevation * rnorm(n = N, mean = 5)))
)

my_data_2 <- resample_data(my_data, N = c(3, 5), ID_labels = c("cities", "citizens"))
my_data_2
##    cities elevation citizens income
## 1       1  1941.207        3  12747
## 2       1  1941.207        3  12747
## 3       1  1941.207        3  12747
## 4       1  1941.207        2   8524
## 5       1  1941.207        2   8524
## 6       1  1941.207        2   8524
## 7       1  1941.207        2   8524
## 8       1  1941.207        2   8524
## 9       1  1941.207        2   8524
## 10      1  1941.207        1   9949
## 11      1  1941.207        1   9949
## 12      1  1941.207        1   9949
## 13      1  1941.207        1   9949
## 14      1  1941.207        1   9949
## 15      1  1941.207        1   9949

## Ns that vary

When making hierarchical data, you may not want to have the same number of units at each level of the hierarchy. For example, in the example below, we want one city to have 2 citizens and the other city to have four:

my_data <-
fabricate(
cities = level(N = 2, elevation = runif(n = N, min = 1000, max = 2000)),
citizens = level(N = c(2, 4), income = round(elevation * rnorm(n = N, mean = 5)))
)
my_data
##   cities elevation citizens income
## 1      1  1268.314        1   6200
## 2      1  1268.314        2   5622
## 3      2  1561.877        3   8468
## 4      2  1561.877        4   4951
## 5      2  1561.877        5   6864
## 6      2  1561.877        6   9126

You can even have Ns that are determined by a function, enabling a random number of citizens per city:

my_data <-
fabricate(
cities = level(N = 2, elevation = runif(n = N, min = 1000, max = 2000)),
citizens = level(N = sample(1:6, size = 2, replace = TRUE), income = round(elevation * rnorm(n = N, mean = 5)))
)
my_data
##    cities elevation citizens income
## 1       1  1989.295       01  13104
## 2       1  1989.295       02   8905
## 3       1  1989.295       03  15421
## 4       1  1989.295       04  10432
## 5       2  1068.203       05   5931
## 6       2  1068.203       06   5902
## 7       2  1068.203       07   4814
## 8       2  1068.203       08   5204
## 9       2  1068.203       09   6509
## 10      2  1068.203       10   4036

## Bringing in your own hierarchical data

Suppose you had existing hierarchical data, and you wanted to add variables that respected the levels.

my_baseline_data <-
fabricate(
cities = level(N = 2, elevation = runif(n = N, min = 1000, max = 2000)),
citizens = level(N = 3, income = round(elevation * rnorm(n = N, mean = 5)))
)

# add new variables at each level
my_data <-
fabricate(data = my_baseline_data,
cities = level(density = elevation / 2),
citizens = level(wealth = income - 100))

my_data
##   citizens cities income elevation  density wealth
## 1        1      1   7303  1405.193 702.5966   7203
## 2        2      1   6772  1405.193 702.5966   6672
## 3        3      1   8510  1405.193 702.5966   8410
## 4        4      2   5089  1138.607 569.3035   4989
## 5        5      2   6965  1138.607 569.3035   6865
## 6        6      2   6243  1138.607 569.3035   6143

# Tidyverse integration

Because the functions in fabricatr take data and return data, they are easily slotted into a tidyverse workflow:

library(dplyr)

# letting higher levels depend on lower levels

my_data <-
fabricate(
cities = level(N = 2, elevation = runif(n = N, min = 1000, max = 2000)),
citizens = level(N = c(2, 3), income = round(elevation * rnorm(n = N, mean = 5)))
) %>%
group_by(cities) %>%
mutate(pop = n())

my_data
## # A tibble: 5 x 5
## # Groups:   cities [2]
##   cities elevation citizens income   pop
##    <chr>     <dbl>    <chr>  <dbl> <int>
## 1      1   1842.06        1   9577     2
## 2      1   1842.06        2   7305     2
## 3      2   1783.04        3  11146     3
## 4      2   1783.04        4   9189     3
## 5      2   1783.04        5   9696     3
my_data <-
data_frame(Y = sample(1:10, 2)) %>%
fabricate(lower_level = level(N = 3, Y2 = Y + rnorm(N)))
my_data
##    Y lower_level        Y2
## 1 10           1 10.495408
## 2 10           2  9.916366
## 3 10           3  9.998652
## 4  6           4  5.288414
## 5  6           5  6.462447
## 6  6           6  6.161634


text:
# $\phi$ meson production in $d$$+$Au collisions at $\sqrt{s_{_{NN}}}=200$ GeV

C92 ( No. )  , p.044909 , 2015-10

Number of accesses :

 Other information

format: plain


text:
# I Finite difference Hamiltonian

1. Sep 19, 2016

### aaaa202

Suppose I am given some 1D Hamiltonian:

H = ħ2/2m d2/dx2 + V(x) (1)

Which I want to solve on the interval [0,L]. I think most of you are familiar with the standard approach of discretizing the interval [0,L] in N pieces and using the finite difference formulas for V and the second derivative in (1), which can then be formulated as a matrix equation, which may be diagonalized for the eigenvector and eigenvalues.
Now for all this to work one has to assume that the wave-function goes to zero outside the interval [0,L], which follows if one makes the effort of writing up the finite difference expressions. My question is: Is there a way to enforce another boundary condition with this method? I am solving a problem, where it would be beneficial to enforce the wave function to take a non-zero value on the boundaries of the interval [0,L]. Is this possible with the standard finite difference method or should I look at more advanced methods?

2. Sep 19, 2016

### Dr Transport

you just have to include the areas outside of the $[0,L]$ in the discretization, the wave function will fall off to 0 depending on the structure of the potential.


text:
1. ## bijection

It is given that
(1) f: A --> B is injective iff f has a left inverse. (f has a left inverse if there is a function g: B --> A such that g(f(a)) = a for all a in A)
(2) f is surjective iff f has a right inverse. (f has a right inverse if there is a function g: B --> A such that f(g(b)) = b for all b in B)

I need to prove that
f is a bijection iff there exists g: B --> A such that f(g(b)) = b for every b in B and g(f(a)) = a for every a in A.

So if I am given (1) and (2) above, can I prove it like this?
i. Suppose f is bijective. That is, f is injective and surjective. Then by (1) there is a function g: B --> A such that g(f(a)) = a for every a in A since f is injective, and by (2) f(g(b)) = b for every b in B. Thus, g is the inverse of f.
ii. Suppose f has an inverse g: B --> A such that f(g(b)) = b for every b in B and g(f(a)) = a for every a in A. Then by (1) and (2) f is injective and surjective. Therefore, f is bijective.

Will this work?

2. Originally Posted by dori1123
It is given that
(1) f: A --> B is injective iff f has a left inverse. (f has a left inverse if there is a function g: B --> A such that g(f(a)) = a for all a in A)
Let me do this one and you try the other one.

Say $f: A\to B$ is injective. Define a function $g:B\to A$ in the following way: let $b\in B$ if $b=f(a)$ for $a\in A$ then define $g(b) = a$ otherwise define $g(b) = b$. It is important to show this is well-defined meaning it makes sense how we defined this function. Perhaps there are several values of $a$ such that $b=f(a)$ - if so then which one do we choose for $g(b) = a$ ? This is not a problem because the function is injective thus these values of $a$ are unique. This defines a function $g: B\to A$. Now we need to confirm that $g(f(a)) =a$. And this is of course true on how we defined $g$ above.

You try the converse and the second part.


text:
Question

# A 5kg steel ball is dropped onto a copper plate from a heightof 10m. If the ball leaves a dent 3.2mm deep, what is the averageforce exerted by the plate on the ball during impact?

Other
A 5kg steel ball is dropped onto a copper plate from a heightof 10m. If the ball leaves a dent 3.2mm deep, what is the averageforce exerted by the plate on the ball during impact?

$$\displaystyle{K}_{{i}}+?{W}={K}_{{f}}$$
$$\displaystyle{0}+{\left[{F}_{{g}}\triangle{y}{\cos{{0}}}+{F}_{{p}}\triangle{x}{\cos{{180}}}\right]}={0}$$
$$\displaystyle{0}+{m}{g{{\left({10}\right)}}}-{F}_{{p}}{\left({0.00320}\right)}={0}$$
Or $$\displaystyle{F}_{{p}}={1.53}\cdot{10}^{{5}}$$


text:
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Fishing Prince loves trees, and he especially loves trees with only one centroid. The tree is a connected graph without cycles.

A vertex is a centroid of a tree only when you cut this vertex (remove it and remove all edges from this vertex), the size of the largest connected component of the remaining graph is the smallest possible.

For example, the centroid of the following tree is $2$, because when you cut it, the size of the largest connected component of the remaining graph is $2$ and it can't be smaller.

However, in some trees, there might be more than one centroid, for example:

Both vertex $1$ and vertex $2$ are centroids because the size of the largest connected component is $3$ after cutting each of them.

Now Fishing Prince has a tree. He should cut one edge of the tree (it means to remove the edge). After that, he should add one edge. The resulting graph after these two operations should be a tree. He can add the edge that he cut.

He wants the centroid of the resulting tree to be unique. Help him and find any possible way to make the operations. It can be proved, that at least one such way always exists.

Input

The input consists of multiple test cases. The first line contains an integer $t$ ($1\leq t\leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($3\leq n\leq 10^5$) — the number of vertices.

Each of the next $n-1$ lines contains two integers $x, y$ ($1\leq x,y\leq n$). It means, that there exists an edge connecting vertices $x$ and $y$.

It's guaranteed that the given graph is a tree.

It's guaranteed that the sum of $n$ for all test cases does not exceed $10^5$.

Output

For each test case, print two lines.

In the first line print two integers $x_1, y_1$ ($1 \leq x_1, y_1 \leq n$), which means you cut the edge between vertices $x_1$ and $y_1$. There should exist edge connecting vertices $x_1$ and $y_1$.

In the second line print two integers $x_2, y_2$ ($1 \leq x_2, y_2 \leq n$), which means you add the edge between vertices $x_2$ and $y_2$.

The graph after these two operations should be a tree.

If there are multiple solutions you can print any.

Example
Input
2
5
1 2
1 3
2 4
2 5
6
1 2
1 3
1 4
2 5
2 6

Output
1 2
1 2
1 3
2 3
Note

Note that you can add the same edge that you cut.

In the first test case, after cutting and adding the same edge, the vertex $2$ is still the only centroid.

In the second test case, the vertex $2$ becomes the only centroid after cutting the edge between vertices $1$ and $3$ and adding the edge between vertices $2$ and $3$.


text: dc.contributor.author Kadin, Jim en_US dc.date.accessioned 2007-04-23T17:24:27Z dc.date.available 2007-04-23T17:24:27Z dc.date.issued 1988-03 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-900 en_US dc.identifier.uri https://hdl.handle.net/1813/6740 dc.description.abstract The polynomialtime many-one and Turing reducibilities, Karp and Cook reducibilities respectively, play an major role in computational complexity theory, particularly in the study of such classes as P, NP, the polynomial time hierarchy (PH), and PSPACE. In this thesis, we consider polynomial time Turing reducibilities with various restricted oracle access mechanisms such as restrictions on the number of queries allowed or requiring that all queries be made at once, in parallel. Such restrictions are related to polynomial time truth-table and bounded truth-table reducibilities. We focus mostly on classes of languages reducible to NP sets via these reducibilities. For any integer $k, P^{NP[k]}$ is the class of languages recognizable in polynomial time with $k$ queries to an oracle from NP. The query hierarchy, QH, is $\bigcup_{k} P^{NP[k]}$. The class $P^{NP[\log n]}$ is the set of languages recognizable with $O(\log n)$ queries. Two related hierarchies are the Boolean hierarchy Boolean hierarchy (BH) and the parallel query hierarchy $(\rm QH_{||})$. The BH, QH, and $\rm QH_{||}$ intertwine to form a rich structure within $P^{NP}$: NP $\cup$ co-NP $\subseteq P^{NP[1]} \subseteq P^{NP[2]} \subseteq \cdots \subseteq QH = QH_{||} = BH \subseteq P^{NP[\log n]} \subseteq P^{NP}.$ We show that the structure of these classes is closely tied to the existence of nonuniform algorithms for NP and co-NP languages and to the structure of the PH as a whole. We improve Mahaney's result for sparse Turing-complete sets for NP by showing that if there exists a sparse set $S \in NP$ such that co-NP $\subseteq NP^{S}$, then PH $\subseteq P^{NP[\log n]}$. We show that there are relativized worlds where this collapse is optimal, and thus we provide a clear distinction between the effects of a sparse many-one-complete set and a sparse Turing-complete set for NP. We prove that if the BH, QH, or $QH_{||}$ collapses, for instance, if $D^{P} =$co-$D^{P}$ or if $P^{NP[k]} = P^{NP[k+1]}$, then there exists a sparse set $S$ such that co-NP $\subseteq$NP^{S}$, and therefore the PH collapses to$P^{NP^{NP}[\log n]}$, a subclass of the$\Delta^{P}_{3}\$ level of the PH. Hence the structure of unsatisfiable Boolean formulas, co-NP, and the whole PH are all closely related to the structure of the BH and to the issue of how deterministic polynomial time algorithms can access the information from NP oracles. en_US dc.format.extent 8098362 bytes dc.format.extent 1513865 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject computer science en_US dc.subject technical report en_US dc.title Restricted Turing Reducibilities and the Structure of the Polynomial Time Hierarchy en_US dc.type technical report en_US


text:
# Add content behind beamer background (or theme)

I have a custom beamer template that frames the content of each slide, like the standard themes but with wiggly header/footer lines.

I add the background image of the template with

\setbeamertemplate{background}
{\includegraphics[width=\paperwidth,height=\paperheight]{master.png}}

I now want the content to be behind the background image and the rest of the template (title, page number...). The template will then have a cut-out with the content visible underneath. The background image can have .png or .pdf transparency.

Does anyone have an idea how to move the content behind the background image?

Thank you for your help!

• How about including the image with textpos in the footline? According to tex.stackexchange.com/questions/26299/… this should be the component drawn as the top layer Apr 3 '14 at 16:53
• nice idea. I tried but unfortunately this overwrites the title. Including it before the title let's it remain under the content. So I guess my question includes: how do I make the title come into foreground? Apr 4 '14 at 17:57
• mmm, that is too bad. Could you share an example of your code? It would be easier to modify an existing code in order to find an solution instead of having to write own stuff ... Apr 4 '14 at 18:02
• How about leaving the traditional title layer empty and including the title in the footline layer [after the passpartout]? Apr 4 '14 at 18:06
• Since you have some responses below that seem to answer your question, please consider marking one of them as ‘Accepted’ by clicking on the tickmark below their vote count (see How do you accept an answer?). This shows which answer helped you most, and it assigns reputation points to the author of the answer (and to you!). It's part of this site's idea to identify good questions and answers through upvotes and acceptance of answers. Nov 21 '16 at 16:22

## 2 Answers

In order to have the title in front of the picture: How about leaving the traditional frametitle layer empty and including the frametitle in the footline layer?

\documentclass[t]{beamer}

\setbeamercolor{background canvas}{bg=blue!20}
\setbeamerfont{frametitle}{size=\fontsize{24}{28},series=\bfseries}
\setbeamercolor{frametitle}{fg=white}

\pgfdeclareimage[width=\paperwidth]{mybackground}{back.pdf}

\providecommand\insertframetitle{}
\setbeamertemplate{footline}{%
\begin{picture}(0,0)
\put(0,0){%
\pgfuseimage{mybackground}
}
\put(25,220){%
\begin{minipage}[b][0mm][t]{100mm}
\usebeamerfont{frametitle}{
\usebeamercolor[fg]{frametitle}{
\insertframetitle
}
}
\end{minipage}
}
\end{picture}
}

\setbeamertemplate{frametitle}{\vspace*{2.5cm}}

\begin{document}

\begin{frame}
\frametitle{Test Test Test}
test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test test  test
\end{frame}

\end{document}

You could try overlaying the image using textpos or tikz, instead of setting it as the background.


text:
D2. Supercollider
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This problem consists of two subproblems: for solving subproblem D1 you will receive 3 points, and for solving subproblem D2 you will receive 16 points.

Manao is the chief architect involved in planning a new supercollider. He has to identify a plot of land where the largest possible supercollider can be built. The supercollider he is building requires four-way orthogonal collisions of particles traveling at the same speed, so it will consist of four accelerating chambers and be shaped like a plus sign (i.e., +). Each of the four accelerating chambers must be the same length and must be aligned with the Earth's magnetic field (parallel or orthogonal) to minimize interference.

The accelerating chambers need to be laid down across long flat stretches of land to keep costs under control. Thus, Manao has already commissioned a topographical study that has identified all possible maximal length tracts of land available for building accelerating chambers that are either parallel or orthogonal to the Earth's magnetic field. To build the largest possible supercollider, Manao must identify the largest symmetric plus shape from among these candidate tracts. That is, he must find the two tracts of land that form an axis-aligned plus shape with the largest distance from the center of the plus to the tip of the shortest of the four arms of the plus. Note that the collider need not use the entire length of the tracts identified (see the example in the notes).

Input

The first line of the input will contain two single-space-separated integers n, the number of north-south tracts and m, the number of west-east tracts.

Each of the n lines following the first describes a north-south tract. Each such tract is described by three single-space-separated integers xi, yi, li representing the vertical line segment from (xi, yi) to (xi, yi + li).

Similarly, after the n lines describing north-south tracts follow m similar lines describing the west-east tracts. Each such tract is described by three single-space-separated integers xi, yi, li representing the horizontal line segment from (xi, yi) to (xi + li, yi).

All xi and yi are between -100000000 and 100000000, inclusive. All li are between 1 and 100000000, inclusive. No pair of horizontal segments will touch or intersect, and no pair of vertical segments will touch or intersect.

The problem consists of two subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.

• In subproblem D1 (3 points), n and m will be between 1 and 1000, inclusive.
• In subproblem D2 (16 points), n and m will be between 1 and 50000, inclusive.
Output

Print one line containing a single integer, the size of the largest supercollider that can be built on one north-south tract and one west-east tract. The size of the supercollider is defined to be the length of one of the four accelerating chambers. In other words, the size of the resulting supercollider is defined to be the distance from the intersection of the two line segments to the closest endpoint of either of the two segments. If no pair of north-south and west-east tracts intersects, it is not possible to build a supercollider and the program should report a maximum size of zero.

Examples
Input
1 24 0 91 1 81 2 7
Output
2
Note

Consider the example. There is one vertical line segment from (4, 0) to (4, 9) and two horizontal line segments: from (1, 1) to (9, 1) and from (1, 2) to (8, 2). The largest plus shape that can be found among these segments is formed from the only vertical segment and the second of horizontal segments, and is centered at (4, 2).

The program should output 2 because the closest end point of those segments to the center is (4, 0), which is distance 2 from the center point of (4, 2). The collider will be formed by the line segments from (2, 2) to (6, 2) and from (4, 0) to (4, 4).


text:
`int_4^oo 1/(x(lnx)^3) dx` Determine whether the integral diverges or converges. Evaluate the integral if it converges.

`int_4^infty 1/(x(ln x)^3)dx=`

Substitute `u=ln x` `=>` `du=1/x dx,` `u_l=ln 4,` `u_u=ln infty=infty` (`u_l` and `u_u` denote lower and upper bound respectively).

`int_(ln 4)^infty1/u^3 du=-1/(2u^2)|_(ln4)^infty=-1/2(lim_(u to infty)1/u^2-1/(ln 4)^2)=-1/2(0-1/(ln 4)^2)=`

`1/(2(ln 4)^2)approx0.260171`

As we can see the integral converges and its value is `1/(2(ln 4)^2).`

The image below shows graph of the function and area under it representing the value of the integral. Looking at the image we can see that the graph approaches -axis (function converges to zero) "very fast". This suggests that the integral should converge to some finite number.

Images:
This image has been Flagged as inappropriate Click to unflag
Image (1 of 1)
Approved by eNotes Editorial Team


text:
# Divergence Calculator

The calculator will find the divergence of the given vector field, with steps shown.

Related calculators: Partial Derivative Calculator, Vector Dot (Inner) Product Calculator

$\langle$
,
,
$\rangle$
$($
,
,
$)$
Leave empty, if you don't need the divergence at a specific point.

If the calculator did not compute something or you have identified an error, or you have a suggestion/feedback, please write it in the comments below.

Calculate $\text{div} \left\langle \sin{\left(x y \right)}, \cos{\left(x y \right)}, e^{z}\right\rangle$.

## Solution

By definition, $\text{div} \left\langle \sin{\left(x y \right)}, \cos{\left(x y \right)}, e^{z}\right\rangle = \nabla\cdot \left\langle \sin{\left(x y \right)}, \cos{\left(x y \right)}, e^{z}\right\rangle$, or, equivalently, $\text{div} \left\langle \sin{\left(x y \right)}, \cos{\left(x y \right)}, e^{z}\right\rangle = \left\langle \frac{\partial}{\partial x}, \frac{\partial}{\partial y}, \frac{\partial}{\partial z}\right\rangle\cdot \left\langle \sin{\left(x y \right)}, \cos{\left(x y \right)}, e^{z}\right\rangle$, where $\cdot$ is the dot product operator.

Thus, $\text{div} \left\langle \sin{\left(x y \right)}, \cos{\left(x y \right)}, e^{z}\right\rangle = \frac{\partial}{\partial x} \left(\sin{\left(x y \right)}\right) + \frac{\partial}{\partial y} \left(\cos{\left(x y \right)}\right) + \frac{\partial}{\partial z} \left(e^{z}\right).$

Find the partial derivative of component 1 with respect to $x$: $\frac{\partial}{\partial x} \left(\sin{\left(x y \right)}\right) = y \cos{\left(x y \right)}$ (for steps, see derivative calculator).

Find the partial derivative of component 2 with respect to $y$: $\frac{\partial}{\partial y} \left(\cos{\left(x y \right)}\right) = - x \sin{\left(x y \right)}$ (for steps, see derivative calculator).

Find the partial derivative of component 3 with respect to $z$: $\frac{\partial}{\partial z} \left(e^{z}\right) = e^{z}$ (for steps, see derivative calculator).

Now, just sum up the above expressions to get the divergence: $\text{div} \left\langle \sin{\left(x y \right)}, \cos{\left(x y \right)}, e^{z}\right\rangle = - x \sin{\left(x y \right)} + y \cos{\left(x y \right)} + e^{z}.$

$\text{div} \left\langle \sin{\left(x y \right)}, \cos{\left(x y \right)}, e^{z}\right\rangle = - x \sin{\left(x y \right)} + y \cos{\left(x y \right)} + e^{z}$A


text:
# How to estimate the accuracy upper limit of any CNN model over a computer vision classification task

We are given a computer vision classification task, that is, a task that asks us to predict the category of an image over $$n$$ predefined classes (the so-called closed set classification problem).

Question: Is it possible to give an estimate on what is the best accuracy one is likely achieve using an end-to-end CNN model (possibly, using a popular backbone) in this task? Do the performances of state-of-the-arts models on open datasets serve as a good reference? If someone claims that they achieve certain performance with some popular CNN architecture, how do we know s/he is not bragging?

You may or may not have access to the training dataset yet. The testing dataset shall be something close to the real-world production scenario. I know this is too vague, but just assume you have a fair judge.

Background: Product teams sometimes asks engineering teams for quick (and dirty) solutions. Engineering teams want to assess the feasibility before say "Yes we can do $$95\%$$" and officially launch (and be responsible) the projects.

• If the task is similar, you can have an estimate of performance from the state-of-the-art. E.g. if you want to build a facial recognition CNN, you can more or less know what to expect. This assumes that your dataset somewhat follows those that the sota is benchmarked upon. In different tasks you have no chance at all to see what you are expecting. – Djib2011 Mar 31 '20 at 0:13


text:
# sklearn.linear_model.ElasticNet¶

class sklearn.linear_model.ElasticNet(alpha=1.0, l1_ratio=0.5, fit_intercept=True, normalize=False, precompute=False, max_iter=1000, copy_X=True, tol=0.0001, warm_start=False, positive=False, random_state=None, selection=’cyclic’)[source]

Linear regression with combined L1 and L2 priors as regularizer.

Minimizes the objective function:

1 / (2 * n_samples) * ||y - Xw||^2_2
+ alpha * l1_ratio * ||w||_1
+ 0.5 * alpha * (1 - l1_ratio) * ||w||^2_2

If you are interested in controlling the L1 and L2 penalty separately, keep in mind that this is equivalent to:

a * L1 + b * L2

where:

alpha = a + b and l1_ratio = a / (a + b)

The parameter l1_ratio corresponds to alpha in the glmnet R package while alpha corresponds to the lambda parameter in glmnet. Specifically, l1_ratio = 1 is the lasso penalty. Currently, l1_ratio <= 0.01 is not reliable, unless you supply your own sequence of alpha.

Read more in the User Guide.

Parameters: alpha : float, optional Constant that multiplies the penalty terms. Defaults to 1.0. See the notes for the exact mathematical meaning of this parameter.alpha = 0 is equivalent to an ordinary least square, solved by the LinearRegression object. For numerical reasons, using alpha = 0 with the Lasso object is not advised. Given this, you should use the LinearRegression object. l1_ratio : float The ElasticNet mixing parameter, with 0 <= l1_ratio <= 1. For l1_ratio = 0 the penalty is an L2 penalty. For l1_ratio = 1 it is an L1 penalty. For 0 < l1_ratio < 1, the penalty is a combination of L1 and L2. fit_intercept : bool Whether the intercept should be estimated or not. If False, the data is assumed to be already centered. normalize : boolean, optional, default False This parameter is ignored when fit_intercept is set to False. If True, the regressors X will be normalized before regression by subtracting the mean and dividing by the l2-norm. If you wish to standardize, please use sklearn.preprocessing.StandardScaler before calling fit on an estimator with normalize=False. precompute : True | False | array-like Whether to use a precomputed Gram matrix to speed up calculations. The Gram matrix can also be passed as argument. For sparse input this option is always True to preserve sparsity. max_iter : int, optional The maximum number of iterations copy_X : boolean, optional, default True If True, X will be copied; else, it may be overwritten. tol : float, optional The tolerance for the optimization: if the updates are smaller than tol, the optimization code checks the dual gap for optimality and continues until it is smaller than tol. warm_start : bool, optional When set to True, reuse the solution of the previous call to fit as initialization, otherwise, just erase the previous solution. See the Glossary. positive : bool, optional When set to True, forces the coefficients to be positive. random_state : int, RandomState instance or None, optional, default None The seed of the pseudo random number generator that selects a random feature to update. If int, random_state is the seed used by the random number generator; If RandomState instance, random_state is the random number generator; If None, the random number generator is the RandomState instance used by np.random. Used when selection == ‘random’. selection : str, default ‘cyclic’ If set to ‘random’, a random coefficient is updated every iteration rather than looping over features sequentially by default. This (setting to ‘random’) often leads to significantly faster convergence especially when tol is higher than 1e-4. coef_ : array, shape (n_features,) | (n_targets, n_features) parameter vector (w in the cost function formula) sparse_coef_ : scipy.sparse matrix, shape (n_features, 1) | (n_targets, n_features) sparse representation of the fitted coef_ intercept_ : float | array, shape (n_targets,) independent term in decision function. n_iter_ : array-like, shape (n_targets,) number of iterations run by the coordinate descent solver to reach the specified tolerance.

ElasticNetCV
Elastic net model with best model selection by cross-validation.
SGDRegressor
implements elastic net regression with incremental training.
SGDClassifier
implements logistic regression with elastic net penalty (SGDClassifier(loss="log", penalty="elasticnet")).

Notes

To avoid unnecessary memory duplication the X argument of the fit method should be directly passed as a Fortran-contiguous numpy array.

Examples

>>> from sklearn.linear_model import ElasticNet
>>> from sklearn.datasets import make_regression
>>>
>>> X, y = make_regression(n_features=2, random_state=0)
>>> regr = ElasticNet(random_state=0)
>>> regr.fit(X, y)
ElasticNet(alpha=1.0, copy_X=True, fit_intercept=True, l1_ratio=0.5,
max_iter=1000, normalize=False, positive=False, precompute=False,
random_state=0, selection='cyclic', tol=0.0001, warm_start=False)
>>> print(regr.coef_)
[18.83816048 64.55968825]
>>> print(regr.intercept_)
1.451...
>>> print(regr.predict([[0, 0]]))
[1.451...]

Methods

 fit(X, y[, check_input]) Fit model with coordinate descent. get_params([deep]) Get parameters for this estimator. path(X, y[, l1_ratio, eps, n_alphas, …]) Compute elastic net path with coordinate descent predict(X) Predict using the linear model score(X, y[, sample_weight]) Returns the coefficient of determination R^2 of the prediction. set_params(**params) Set the parameters of this estimator.
__init__(alpha=1.0, l1_ratio=0.5, fit_intercept=True, normalize=False, precompute=False, max_iter=1000, copy_X=True, tol=0.0001, warm_start=False, positive=False, random_state=None, selection=’cyclic’)[source]
fit(X, y, check_input=True)[source]

Fit model with coordinate descent.

Parameters: X : ndarray or scipy.sparse matrix, (n_samples, n_features) Data y : ndarray, shape (n_samples,) or (n_samples, n_targets) Target. Will be cast to X’s dtype if necessary check_input : boolean, (default=True) Allow to bypass several input checking. Don’t use this parameter unless you know what you do.

Notes

Coordinate descent is an algorithm that considers each column of data at a time hence it will automatically convert the X input as a Fortran-contiguous numpy array if necessary.

To avoid memory re-allocation it is advised to allocate the initial data in memory directly using that format.

get_params(deep=True)[source]

Get parameters for this estimator.

Parameters: deep : boolean, optional If True, will return the parameters for this estimator and contained subobjects that are estimators. params : mapping of string to any Parameter names mapped to their values.
static path(X, y, l1_ratio=0.5, eps=0.001, n_alphas=100, alphas=None, precompute=’auto’, Xy=None, copy_X=True, coef_init=None, verbose=False, return_n_iter=False, positive=False, check_input=True, **params)[source]

Compute elastic net path with coordinate descent

The elastic net optimization function varies for mono and multi-outputs.

1 / (2 * n_samples) * ||y - Xw||^2_2
+ alpha * l1_ratio * ||w||_1
+ 0.5 * alpha * (1 - l1_ratio) * ||w||^2_2

(1 / (2 * n_samples)) * ||Y - XW||^Fro_2
+ alpha * l1_ratio * ||W||_21
+ 0.5 * alpha * (1 - l1_ratio) * ||W||_Fro^2

Where:

||W||_21 = \sum_i \sqrt{\sum_j w_{ij}^2}

i.e. the sum of norm of each row.

Read more in the User Guide.

Parameters: X : {array-like}, shape (n_samples, n_features) Training data. Pass directly as Fortran-contiguous data to avoid unnecessary memory duplication. If y is mono-output then X can be sparse. y : ndarray, shape (n_samples,) or (n_samples, n_outputs) Target values l1_ratio : float, optional float between 0 and 1 passed to elastic net (scaling between l1 and l2 penalties). l1_ratio=1 corresponds to the Lasso eps : float Length of the path. eps=1e-3 means that alpha_min / alpha_max = 1e-3 n_alphas : int, optional Number of alphas along the regularization path alphas : ndarray, optional List of alphas where to compute the models. If None alphas are set automatically precompute : True | False | ‘auto’ | array-like Whether to use a precomputed Gram matrix to speed up calculations. If set to 'auto' let us decide. The Gram matrix can also be passed as argument. Xy : array-like, optional Xy = np.dot(X.T, y) that can be precomputed. It is useful only when the Gram matrix is precomputed. copy_X : boolean, optional, default True If True, X will be copied; else, it may be overwritten. coef_init : array, shape (n_features, ) | None The initial values of the coefficients. verbose : bool or integer Amount of verbosity. return_n_iter : bool whether to return the number of iterations or not. positive : bool, default False If set to True, forces coefficients to be positive. (Only allowed when y.ndim == 1). check_input : bool, default True Skip input validation checks, including the Gram matrix when provided assuming there are handled by the caller when check_input=False. **params : kwargs keyword arguments passed to the coordinate descent solver. alphas : array, shape (n_alphas,) The alphas along the path where models are computed. coefs : array, shape (n_features, n_alphas) or (n_outputs, n_features, n_alphas) Coefficients along the path. dual_gaps : array, shape (n_alphas,) The dual gaps at the end of the optimization for each alpha. n_iters : array-like, shape (n_alphas,) The number of iterations taken by the coordinate descent optimizer to reach the specified tolerance for each alpha. (Is returned when return_n_iter is set to True).

Notes

For an example, see examples/linear_model/plot_lasso_coordinate_descent_path.py.

predict(X)[source]

Predict using the linear model

Parameters: X : array_like or sparse matrix, shape (n_samples, n_features) Samples. C : array, shape (n_samples,) Returns predicted values.
score(X, y, sample_weight=None)[source]

Returns the coefficient of determination R^2 of the prediction.

The coefficient R^2 is defined as (1 - u/v), where u is the residual sum of squares ((y_true - y_pred) ** 2).sum() and v is the total sum of squares ((y_true - y_true.mean()) ** 2).sum(). The best possible score is 1.0 and it can be negative (because the model can be arbitrarily worse). A constant model that always predicts the expected value of y, disregarding the input features, would get a R^2 score of 0.0.

Parameters: X : array-like, shape = (n_samples, n_features) Test samples. For some estimators this may be a precomputed kernel matrix instead, shape = (n_samples, n_samples_fitted], where n_samples_fitted is the number of samples used in the fitting for the estimator. y : array-like, shape = (n_samples) or (n_samples, n_outputs) True values for X. sample_weight : array-like, shape = [n_samples], optional Sample weights. score : float R^2 of self.predict(X) wrt. y.
set_params(**params)[source]

Set the parameters of this estimator.

The method works on simple estimators as well as on nested objects (such as pipelines). The latter have parameters of the form <component>__<parameter> so that it’s possible to update each component of a nested object.

Returns: self
sparse_coef_

sparse representation of the fitted coef_


text:
World's most popular travel blog for travel bloggers.

# Positive Definiteness Constraint

, ,
Problem Detail:

I want to add a constraint to a convex program, to guarantee some matrix $A$ to be positive semidefinite. How should I do it?

The library I am working with can cope with linear/ quadratic inequalities only.

By definition, $A$ is positive semidefinite iff $\forall x \in \mathbb C^n : x^T A x \geq 0$, but this is a set of inifinitely many constraints. So, my question is: how can I formulate it using a finitely many set of contraints and using linear/ quadratic inequalities only.

###### Asked By : Dudi Frid

A matrix $A$ is positive semidefinite if and only if there exists a matrix $V$ such that $$A = V^\top V.$$ So, you can use the entries of $V$ as your unknowns, and express each entry of $A$ as a quadratic function of the unknowns. Whenever you want to use $A$, instead rewrite that equation in terms of the entries of $V$.


text:
# How to make countably closed forcing “nice” without choice

When working over a model $V$ of $ZFC$, countably closed forcings are extremely nice:

If $\mathbb{P}$ is countably closed, then $V[G]$ has no new $\omega$-sequences of elements of $V$. In particular, countably closed forcing adds no new reals.

This can fail miserably if $V\models ZF+\neg AC$. In particular, it is consistent with $ZF$ that there is an infinite, Dedekind-finite set $X$ of reals. Letting $\mathbb{P}$ be the poset of finite partial injective maps $\subseteq\omega\rightarrow X$, we have the peculiar result that $\mathbb{P}$ is countably closed inside $V$, since there are no countably infinite subsets of $X$!

The general question is: without $AC$, what are good ways to tell that forcing with a given poset adds no new reals?

A particular sub-question, that I am separately interested in: if $W\models ZF$, $W$ is an inner model of $V\models ZFC$ with $\mathbb{R}^V=\mathbb{R}^W$, and $\mathbb{P}\in W$ is countably closed in $V$, then forcing with $\mathbb{P}$ over $W$ adds no new reals. However, I don't actually know any ways of building pairs $(V, W)$ with these properties. So, my subquestion is:

How does one show (without extra consistency strength, so not $L(\mathbb{R})$) that there are models $V$ and $W$ of $ZFC$ and $ZF$ respectively, such that $W\models$ "The reals are not well-ordered" and $\mathbb{R}^V=\mathbb{R}^W$?

-
Have you said what you meant in the last sentence? Probably you mean that $W$ satisfies only ZF, since it has no well-order of $\mathbb{R}$. –  Joel David Hamkins Aug 12 '13 at 23:30
Quite right, fixed. –  Noah S Aug 13 '13 at 3:06

This is actually a question I am quite concern with at the moment. In its generality, let me give a slight re-hash of what Joel said, with perhaps a slight generalization.$\newcommand{\forces}{\Vdash}$

We say that $\Bbb P$ is $\kappa$-closed if every decreasing sequence of length $\kappa$ (or shorter) has a lower bound. We say that $\Bbb P$ is $\kappa$-Baire (or $\kappa$-distributive) if the intersection of $\kappa$ many dense open sets is dense (and open, trivially).

In $\sf ZF$ we can prove these two theorems:

Theorem I. If $\Bbb P$ is a $\kappa$-Baire forcing then $\Bbb P$ does not add new subsets of size $\leq\kappa$ to the universe.

Proof. Suppose that $p\forces\dot f\colon\check\kappa\to\check V$. By the definition of the forcing relation, for every $\alpha<\kappa$ we have a dense set $$D_\alpha=\{q\leq p\mid\exists x\in V, q\forces\dot f(\check\alpha)=\check x\}.$$

Let $D$ be the intersection of these dense open sets, then by the $\kappa$-Baire property $D$ is dense, and therefore non-empty. Let $q\in D$ then for every $\alpha<\kappa$ there is some $x\in V$ such that $q\forces\dot f(\check\alpha)=\check x$. However $q$ forces that $\dot f$ is a function, therefore this $x$ must be unique. If so the function $g(\alpha)=x$ for which $q\forces\dot f(\check\alpha)=\check x$ is such for which $q\forces\check g=\dot f$, as wanted. $\square$

Theorem II. $\sf DC_\kappa$ holds if and only if every $\kappa$-closed forcing is $\kappa$-Baire.

Proof. Suppose that $\sf DC_\kappa$ holds, the proof goes the same as in $\sf ZFC$. In the other direction, recall that $\sf DC_\kappa$ is equivalent to the following statement:

• Every tree $T$ of height $\kappa$, where every sequence of $<\kappa$ has a proper end extension has a branch of length $\kappa$.

Suppose now that $\sf DC_\kappa$ fails, then there is a tree $T$ of height $\kappa$ in which every sequence can be extended, but there is no branch of length $\kappa$. Define $P$ to be the reverse tree order on $T$. This forcing is trivially $\kappa$-closed, because there are no decreasing sequences of length $\kappa$. On the other hand, consider the dense sets $\{q\in T\mid\operatorname{lvl}_T(q)>\alpha\}$. Each is dense open, but their intersection is empty. $\square$

Finally, for real numbers. Or more specifically, sets of ordinals. If a forcing is $\kappa$-Baire then it doesn't add any new sets of size $\kappa$, but we are only interested in sets of ordinals.

I haven't managed to figure out the exact property, and working with $\kappa$-Baire forcings seems reasonable enough (and controllable enough).

To your subquestion, without verifying the details (I might do so tomorrow, but feel free to let me know if you do it yourself and find a mistake).

Consider the forcing which adds $\aleph_1$ Cohen generics, i.e. $p\in\Bbb P$ is a finite function from $\omega_1\times\omega$ to $2$, with the usual order. Now apply permutations (perhaps with a finite or countable support) of $\omega_1$ onto the left coordinate of the conditions.

Consider the names which are fixed by a countable subset of $\omega_1$. That is to say, there exists $\alpha<\omega_1$ such that whenever $\pi$ fixes pointwise $\alpha$ (as a set), it fixes the name.

I suspect that you can prove that all the real numbers of $V[G]$ enter this symmetric extension (perhaps by some argument that every real number is decided by some countable subset of the forcing, and therefore we can find it a support).

It is easy to show by the usual arguments, though, that there is no well-ordering of $\Bbb R$ in the symmetric extension.

-
Asaf, thank you very much for this answer. Let me try to fill in the gaps in the final argument: –  Noah S Aug 16 '13 at 19:08
Suppose $a$ is a real in $V[G]$, $a=\nu[G]$. In $V[G]$, I can find countably many conditions $p_i\in G$ such that each $p_i$ decides the first $i$ bits of $a$; in turn, this gives me some countable (in $V[G]$) ordinal $\alpha$ such that each of the $p_i$ have support $\subseteq\alpha$. Now, by the fact that $\mathbb{P}$ is c.c.c., countable-in-$V[G]$ is the same as countable-in-$V$, so $\alpha<\omega_1^V=\omega_1^{V[G]}$. –  Noah S Aug 16 '13 at 19:10
(cont'd) Now let $\mu=\lbrace (p, \sigma): (p, \sigma)\in \nu, Supp(p)<\alpha\rbrace$ (where $Supp(p)$ is the support of $p\in\mathbb{P}$). $\mu$ is clearly a symmetric name, and $\mu[G]=\nu[G]$ by choice of $\alpha$; so this shows that all reals in $V[G]$ have symmetric names. (Of course, this is nonuniform: we do not have $1\Vdash \mu=\nu$, and I don't imagine that we can find a symmetric name $\sigma$ such that $1\Vdash \sigma=\nu$; but that isn't a problem here.) –  Noah S Aug 16 '13 at 19:13
@Noah: Yeah, that's what I had in mind. In simple words, every real in the extension is either in $L$ or it appears in a Cohen extension; therefore every real is fully decided by a countable subforcing. If we use countable supports then every real is symmetric. –  Asaf Karagila Aug 16 '13 at 19:14
Is it obvious that this model does not satisfy $DC$? (I'm thinking of my mathstackexchange question.) –  Noah S Aug 16 '13 at 19:15

This doesn't answer the full version of your question, but it seems pertinent.

Theorem. (Gunter Fuchs) The following are equivalent over ZF:

1. DC

2. Countably-closed forcing does not add new $\omega$-sequences.

Proof. The forward direction is the usual argument. For the converse, suppose DC fails, so there is a relation $R$ on a set $X$ with no terminal nodes and no $\omega$-sequence through it. Let $\mathbb{P}$ be the forcing notion to add a threading $\omega$-sequence through $R$, consisting of finite sequences $\langle a_0,\ldots,a_n\rangle$, with $a_i\mathrel{R} a_{i+1}$, ordered by extension. The assumption ensures that this forcing is countably closed, for reasons similar to the ones you mention in your question. But the generic filter will create a new threading $\omega$-sequence, since every finite sequence can be extended one more node. QED

-
In particular, if you consider not adding $\omega$-sequences in place of not adding reals, then your subquestion is related to the question of whether DC holds in $L(\mathbb{R})$, about which I think a lot is known. –  Joel David Hamkins Aug 12 '13 at 23:35
Eric Hall told me about this theorem in a private correspondence some three years ago; and in YST 2013 me and Thomas Johnstone talked about this a bit and arrived fairly close to the proof (of the second theorem) in my answer. I don't recall whether or not we actually proved it, but using the little notes that I had from our conversations I came up with the theorem and the proof. –  Asaf Karagila Aug 13 '13 at 0:07
I think that Gunter Fuchs made his observation by 2008, and it appears in a paper of his, but I can't recall which one; I'm not sure what the full generality was. I do recall it coming up by him years ago and also with Thomas Johnstone at our seminar. –  Joel David Hamkins Aug 13 '13 at 0:20
It's a cute observation. That's for sure. –  Asaf Karagila Aug 13 '13 at 0:22
I seem to recall Gunter labeling it as an "amusing observation" in his paper... –  Joel David Hamkins Aug 13 '13 at 0:24


text:
MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

I only concern myself with faithful representations of $S_n$ and for $n >4$. The only way to get a polynomial algebra of invariants is to represent $S_n$ as a complex reflection group (so generated by pseudo-reflections, that is elements wih a fixed-point space of codimension $1$). A complex relfection group is easily checked to always be a direct product of ireducible complex reflection groups, so from now on I consider only irreducible representations. The question then becomes: is there an irreducible representation of $S_n$ other than the usual $n-1$-dimensional irreducible constituent of the natural permutation character, where $S_n$ is represented as a complex reflection group? Note that tensoring with the sign representation of the stated $n-1$-dimensional representation does not produce a representation of $S_n$ as a complex reflection group. There is still some content to this question. It can probably be easily addressed by the Murnaghan-Nakayama rule, or from a more detailed knowledge of the character table of $S_n,$ but I attempt a direct argument here. Since the characters of $S_n$ are rational-valued, any element represented as a pseudo reflection in the given representation must be represented as a genuine (or "real") reflection, since its trace must be rational. The generating reflections for $S_n$ in the given representation act with determinant $-1,$ so lie outside the derived group $A_n.$ Hence they are odd permutations, and expressible as a product of an odd number of (disjoint) transpositions, since they have order $2$. Since $A_n$ is simple ( as $n \geq 5$,) any single conjugacy class of these reflections generates the whole of $S_n,$ so we assume that all the generating reflections are conjugate. Note that we are not yet entitled to assume that the generating reflections are transpositions. Now we note that the product of two generating reflections has order $1,2,3,4$ or $6.$ For such a product has a fixed point space of codimension $0$ or $2,$ has determinant $1$, and has a rational trace. Now if $k >1$ is odd, a product of $k$ transpositions inverts a $2k$-cycle 2k+1$-cycle in$S_{2k}.$S_{2k+1}.$ Hence if $k > 3,$ and $n \geq 2k,$ 2k+1,$then$S_{n}$contains a pair of conjugate permutations, each a product of$k$disjoint transpositions, whose product has order$2k.$2k+1.$ hen $n = 2k$ we may express a $2k$-cycle as a product of two permutations, one a product of $k$ disjoint transpositions, the other a product of $k-1$ disjoint transpositions. Since $k > 3,$ if we adjoin a transposition interchanging the fixed points of the second permutation, we get a product of two permutations, each a product of $k$ disjoint transpositions, where the product is a product of two disjoint cycles of lengths (allowing a $1$-cycle) whose sum adds to $n.$ Since $n \geq 10,$ sucha product never has order $1,2,3,4,5$ or $6.$ Hence we can assume that our generating reflections are products of at most three transpositions. Furthermore, if $n \geq 8,$ we can express a $5$-cycle in $S_n$ as a product of permutations, each a product of three disjoint transpositions. For we may express a $5$-cycle in $S_5$ as a product of two permutatons, each a product of two disjoint two-cycles. Affix a transposition commuting with the $5$-cycle to each of them, and this does not change the product. Hence if our reflections are products of $3$ disjoint $2$-cycles, we are left with the case $n =6.$ In fact, this case does occur. "Twist" the natural (non-unimodular) irreducible $5$-dimensional representation of $S_6$ by the exceptional outer automorphism of $S_6,$ and we obtain a reflection representation of $S_6$ in which products of $3$ disjoint $2$-cycles act as reflections. It remains to deal with reflection representations of $S_n$ in which transposition act as reflections. I presume that the Murnaghn-Nakayama rule or the character table of $S_n$ then shows that only the expected representation arises, but I leave that issue open here. (Later Edit: This now seems to be covered by Mark Wildon's answer).
I only concern myself with faithful representations of $S_n$ and for $n >4$. The only way to get a polynomial algebra of invariants is to represent $S_n$ as a complex reflection group (so generated by pseudo-reflections, that is elements wih a fixed-point space of codimension $1$). A complex relfection group is easily checked to always be a direct produt product of ireducible complex reflection groups, so from now on I consider only irreducible representations. The question then becomes, : is there an irreducible representation of $S_n$ other than the usual $n-1$-dimensional irreducible constituent of the natural permutation character, where $S_n$ is represented as a complex reflection group? Not Note that tensoring with the sign representation of the stated $n-1$-dimensional representation does not produce a representation of $S_n$ as a complex reflection group. There is still some content to this question. It can probably be easil easily addressed by the Murnaghan-Nakayama rule, or from a more detailed knowledge of the character table of $S_n,$ but I attempt a direct argument here. Since the chracters characters of $S_n$ are rational valuedrational-valued, any element represented as a pseudo reflection in the given representation must be represented as a genuine (or "real") reflection, since its trace must be rational. The generating reflections for $S_n$ in the given representation act with determinant $-1,$ so lie outside the derived group $A_n.$ Hence they are odd permutations, and expressible as a product of an odd number of (disjoint) transpositions, since they have order $2$. Aince Since $A_n$ is simple ( as $n >5$,) \geq 5$,) any single conjugacy class of these reflections generates the whole of$S_n,$so we assume that all the generating reflections are conjugate. Note that we are not yet entitled to assume that the generating reflections are transpositions. Now we note that the product of two generating reflections has order$1,2,3,4$or$6.$For such a product has a fixed point space of codimension$0$or$2,$has determinant$1$, and has a rational trace. Now if$k >1$is odd, a product of$k$transpositions inverts a$2k$-cycle in$S_{2k}.$Hence if$k > 3,$and$n \geq 2k,$then$S_{n}$contains a pair of conjugate permutations, each a product of$k$disjoint transpositions, whose product has order$2k.$Hence we can assume that our generating reflections are products of at most three transpositions. Furthermore, if$n \geq 8,$we can express a$5$-cycle in$S_n$as a product of permutations, each a product of three disjoint transpositions. For we may express a$5$-cycle in$S_5$as a product of two permutatons, each a product of two disjint disjoint two-cycles. Affix a transposition commuting with the$5$-cycle to each of them, and this does not change the product. Hence if our reflections are products of $$3 3 disjoint 2-cycles, we are left with the case n =6. In fact, this case does occur. "Twist" the natural (non-unimodular) irreducible 5-dimensional representation of S_6 by the exceptional outer automorphism of S_6, and we obtain a reflection representation of S_6 in which products of 3 disjoint 2-cycles act as reflections. It remains to deal with reflection representations of S_n in which transposition act as reflections. I presume that the Murnaghn-Nakayama rule or the character table of S_n then shows that only the expected representation arises, but I leave that issue open here. (Later Edit: This now seems to be covered by Mark Wildon's answer). 2 Minor textual corrections. Reference to resolution of outstanding case. I only concern myself with faithful representations of S_n and for n >4. The only way to get a polynomial algebra of invariants is to represent S_n as a complex reflection group (so generated by pseudo-reflections, that is elements wih a fixed-point space of codimension 1). A complex relfection group is easily checked to always be a direct produt of ireducible complex reflection groups, so from now on I consider only irreducible representations. The question then becomes, is there an irreducible representation of S_n other than the usual n-1-dimensional irreducible constituent of the natural permutation character, where S_n is represented as a complex reflection group? Not that tensoring with the sign representation of the stated n-1-dimensional representation does not produce a representation of S_n as a complex reflection group. There is still some content to this question. It can probably be easil addressed by the Littlewood-Richardson Murnaghan-Nakayama rule, or from a more detailed knowledge of the character table of S_n, but I attempt a direct argument here. Since the chracters of S_n are rational valued, any element represented as a pseudo reflection in the given representation must be represented as a genuine (or "real") reflection, since its trace must be rational. The generating reflections for S_n in the given representation act with determinant -1, so lie outside the derived group A_n. Hence they are odd permutations, and expressible as a product of an odd number of (disjoint) transpositions, since they have order 2. Aince A_n is simple ( as n >5,) any single conjugacy class of these reflections generates the whole of S_n, so we assume that all the generating reflections are conjugate. Note that we are not yet entitled to assume that the generating reflections are transpositions. Now we note that the product of two generating reflections has order 1,2,3,4 or 6. For such a product has a fixed point space of codimension 0 or 2, has determinant 1, and has a rational trace. Now if k >1 is odd, a product of k transpositions inverts a 2k-cycle in S_{2k}. Hence if k > 3, and n \geq 2k, then S_{n} contains a pair of conjugate permutations, each a product of k transpositions, whose product has order 2k. Hence we can assume that our generating reflections are products of at most three transpositions. Furthermore, if n \geq 8, we can express a 5-cycle in S_n as a product of permutations, each a product of three disjoint transpositions. For we may express a 5-cycle in S_5 as a product of two permutatons, each a product of two disjint two-cycles. Affix a transposition commuting with the 5-cycle to each of them, and this does not change the product. Hence if our reflections are products of$$3 disjoint$2$-cycles, we are left with the case$n =6.$In fact, this case does occur. "Twist" the natural (non-unimodular) irreducible$5$-dimensional representation of$S_6$by the exceptional outer automorphism of$S_6,$and we obtain a reflection representation of$S_6$in which products of$3$disjoint$2$-cycles act as reflections. It remains to deal with reflection representations of$S_n$in which transposition act as reflections. I presume that the Littlewood Richardson ule Murnaghn-Nakayama rule or the characte character table of$S_n\$ then shows that only the expected representation arises, but I leave that issue open here. (Later Edit: This now seems to be covered by Mark Wildon's answer).


text:
# Volker's LaTeX Software

The licenses under which I offer this software is either the GPL or the LPPL, as given in the files themselves.

### LaTeX & Co

See the TeX Users' Group (TUG) for more info on LaTeX. Almost all this software is also available from CTAN (the Comprehensive TeX Archive Network).

#### Other:

 dvipsconfig download This is a set of PostScript header files which can be used to control the printer, like simplex/duplex printing, or the printing, like screen frequencies of images, or the addition of a grid underlay. These header files work with dvips, and can also be inserted with the addpsctrl script into existing PostScript files. License: GPL 2 makefonts download A set of Unix shell scripts (Bourne shell) running metafont to generate a full set of tfm and pk files, rather than having them generated on the fly. For LaTeX, AMS, and various other free fonts found on CTAN.

#### Scripts:

 deltex/deltexa download Delete all files generated by latex/bibtex/dvips, of one document or all documents in the given directory(ies). tx download Run latex, makeindex, etc. for the given document. This really cuts down on typing!

#### University of Canterbury Coat of Arms:

 The official graphic files containing the University's Coat of Arms are not well-suited for LaTeX. I have cleaned them up (line breaks, bounding boxes) so the eps files will work properly. There are tiff files as well, and all in different sizes. Until someone complains, get them here (460k).

 home | linux | software | packages| contact
 Copyright © 2001–2006 by Volker Kuhlmann Created: 07 Feb 2001, last updated: 11 May 2006         URL: http://volker.top.geek.nz/soft/index_texmf.html


text:
# What's the difference between ZFC+Grothendieck, ZFC+inaccessible cardinals and Tarski-Grothendieck set theory?

Say that "U" is the axiom that "For each set x, there exists a Grothendieck universe U such that x $\in$ U", where Grothendieck universes are defined in the usual way (or, if that's unclear, in this way). Also, say that "Ca" is the axiom that "For each cardinal κ, there is a strongly inaccessible cardinal $\lambda$ which is strictly larger than κ."

It's known that ZFC+U and ZFC+Ca are completely equivalent and prove the same sentences. A sentence is a theorem of ZFC+U iff it's a theorem of ZFC+Ca.

In addition to the above, there's also Tarski-Grothendieck set theory, which can be found here. The axioms of TG are

1. The axiom stating everything is a set
2. The axiom of extensionality from ZFC
3. The axiom of regularity from ZFC
4. The axiom of pairing from ZFC
5. The axiom of union from ZFC
6. The axiom schema of replacement from ZFC
7. Tarski's axiom A

Tarski's axiom A states that for any set $x$, there exists a set $y$ containing, $x$ itself, every subset of every member of $y$, the power set of every member of $y$, and every subset of $y$ of cardinality less than $y$.

These three axioms from ZFC are then implied as theorems of TG:

1. The axiom of infinity
2. The axiom of power set
3. The axiom schema of specification
4. The axiom of choice

My question is as follows: is TG also completely equivalent to ZFC+U and ZFC+Ca, equivalent in the same sense that something is a theorem of TG iff it's a theorem of the other two? Is TG just an axiomatization of ZFC+U/ZFC+Ca which removes redundant axioms and allows them to just be theorems? Or is there some subtle difference between TG and ZFC+U/ZFC+Ca, in that there's some sentence which TG proves that's undecidable in ZFC+U/ZFC+Ca or vice versa?

In other words, instead of typing ZFC+Grothendieck, can I just type TG and be referencing a different axiomatization of the exact same thing?

-
"C" already denotes the axiom of choice, so it's not the best abbreviation for another axiom. –  John Bentin Jul 22 '12 at 18:58
Fair enough. I'll change it to "Ca". –  Mike Battaglia Jul 23 '12 at 6:54

Yes. Assume ZFC. If there is a proper class of inaccessible cardinals, then Tarski's Axiom A holds because whenever $\kappa$ is inaccessible, the rank initial segment $V_\kappa$ of $V$ is a Tarski set. Conversely, if Tarski's Axiom A holds then for every set $x$ there is a Tarski set $y$ with $x \in y$. We will show that $|y|$ is an inaccessible cardinal greater than $|x|$, proving the existence of a proper class of inaccessible cardinals.

To show that the cardinality $\kappa$ of $y$ is a strong limit cardinal, given $\zeta < \kappa$ we take a subset $z$ of $y$ of size $\zeta$. We have $z \in y$ because $y$ contains its small subsets. Then we have $\mathcal{P}(z) \in y$ because $y$ is closed under the power set operation. Finally $\mathcal{P}(\mathcal{P}(z)) \subset y$ because $y$ contains all subsets of its elements. This shows that $2^{2^{\zeta}} \le \kappa$ and therefore that $2^{\zeta} < \kappa$.

To show that the cardinality $\kappa$ of $y$ is regular, notice that if $\kappa$ is singular then by the closure of $y$ under small subsets we can get a family of $\kappa^{cof(\kappa)}$ many distinct sets in $y$, contradicting the fact that $\kappa^{cof( \kappa)} > \kappa$ (which is an instance of Koenig's Theorem.)

-
I always thought that it was $2$-inaccessible (which is slightly stronger than a proper class of inaccessibles) that was equivalent to the TG axioms. –  Asaf Karagila Jul 22 '12 at 7:13
Is a 2-inaccessible an inaccessible limit of inaccessibles? In this case, if $\kappa$ is 2-inaccessible, then $V_\kappa$ is a model of TG. –  Stefan Geschke Jul 22 '12 at 8:12
Stefan, yes. Indeed if $\kappa$ is $2$-inaccessible then $V_\kappa$ is a model of ZFC+proper class of inaccessible. I suppose that I get the minor difference. –  Asaf Karagila Jul 22 '12 at 9:53
@Mike: I'll respond to your second comment first, regarding my other attempt at answering this question, which I deleted quickly but it looks like you were still notified of. If there is a single inaccessible cardinal then for every $x$ there is a Tarski set $y$ with $\lbrace x \rbrace \in y$, and this implies that there is a proper class of Tarski sets, but it does not imply Tarski's axiom that for every $x$ there is a Tarski set $y$ with $x \in y$. –  Trevor Wilson Jul 23 '12 at 14:25
@Mike: regarding your first comment, modulo ZFC all three axioms are equivalent by what I wrote combined with what you wrote (that ZFC+U and ZFC+Ca are equivalent.) It does seem to be known that Tarski's Axiom A is not equivalent to the other two under ZF for the reason you said. –  Trevor Wilson Jul 23 '12 at 16:34


text:
# Is hyperbolic space consistent with homogeneity?

1. Sep 29, 2014

### center o bass

The FRW metric is usually expressed as
$$ds^2 = -dt^2 + a(t)^2 ( \frac{dr^2}{1-kr} + r^2 d\Omega^2))$$
where $k=-1,0,+1$ respectively for a hyperbolic, flat or spherical space. The spatial part of this metric can be derived by considering a 3-sphere embedded in a four-dimensional flat space -- any sphere obviously being homogeneous.

Similarly, the k=-1 case can be derived by considering a hyperboloid embedded in a flat four dimensional space. Now, the hyperboloid is only a homogeneous space when embedded in a flat minkowskian space -- in Euclidean space the point at the tip of the hyperboloid (corresponding to r=0) is certainly special.

Since it is the euclidean distance we measure when measuring distances to other galaxies, it seems like the k=-1 case is not consistent with homogeneity. Is this correct, or is my thinking wrong?

2. Sep 29, 2014

### Staff: Mentor

The distance we measure is not the Euclidean distance; it's the distance in a spacelike slice of constant cosmological time (i.e., $dt = 0$ in the metric you wrote down), given the metric of the spacelike slice. (Note that we don't directly "measure" this distance either; we calculate it based on other "distance" observations.) None of this has anything to do with how, or whether, you can embed that spacelike slice in a higher-dimensional Euclidean or Minkowskian space. The only requirement for homogeneity is that no point is "special" with reference to the intrinsic metric of the spacelike slice. The $k = -1$ hyperbolic space satisfies that requirement.

3. Sep 30, 2014

### center o bass

I agree that the spatial distance measure is not euclidean; its Minkowskian (see Weinberg Gravitation p. 391) -- so the space is homogeneous only with respect to this metric. However, I would argue that we measure distances in the universe by the Euclidean distance measure, and thus, to us, I would not think that it appears homogeneous regarding the distribution of galaxies etc.

4. Sep 30, 2014

### center o bass

So I agree that the space is homogeneous with regards to the intrinsic metric. However, as we do not use this metric (which has signature -1), my argument is that we do not __see it__ as being homogeneous?

5. Sep 30, 2014

### Staff: Mentor

Why do you think that? The "Euclidean distance measure" is a measure in a higher-dimensional embedding space that doesn't even exist (it's just a mathematical fiction used by some people for modeling).

I'm confused. What "intrinsic" metric do you think we are not using? (If you think we are using the Euclidean metric, see above.)


text:
This is a toy stochastic gradient system which can have bistability in some conditions. Model specification: $$U = x^4 + y^4 + axy + bx + cy$$ $$dx/dt = - \partial U/ \partial x + \sigma dW/dt = - 4x^3 - ay - b + \sigma dW/dt$$ $$dy/dt = - \partial U/ \partial y + \sigma dW/dt = - 4y^3 - ax - c + \sigma dW/dt$$

sim_fun_grad(
initial = list(x = 0, y = 0),
parameter = list(a = -4, b = 0, c = 0, sigmasq = 1),
length = 1e+05,
stepsize = 0.01,
seed = NULL
)

## Arguments

initial, parameter

Two sets of parameters. initial contains the initial value of x and y; parameter contains a,b,c, which control the shape of the potential landscape, and sigmasq, which is the square of $$\sigma$$ and controls the amplitude of noise.

length

The length of simulation.

stepsize

The step size used in the Euler method.

seed

The initial seed that will be passed to set.seed() function.

## Value

A matrix of simulation results.

sim_fun_nongrad() and batch_simulation().