Contractible manifold with boundary - is it a disc?

2010-03-19T22:03:09Z

I'm sure this is standard but I don't know where to look. Let $M$ be a contractible compact smooth $n$-manifold with boundary. Does it have to be homeomorphic to $D^n$? What about diffeomorphic?

[UPDATE: the answer is well-known to be negative as many people kindly pointed out. But actually I assume more about the manifold, namely the following:]

There is a Riemannian metric on $M$ such that every two points are connected by a unique shortest path. So $M$ can be contracted to a point $p\in M$ by sending every point along a shortest path to $p$. These paths can bend along the boundary and can merge because of this. But they are relatively nice (namely $C^{1,1}$) curves and their first derivatives depend continuously on their endpoints. Given all this, can one conclude that $M$ is a disc?

ADDED: These curves are of course gradient curves of a function (the distance to $p$) which is $C^1$ and has no critical points in the interior of $M$, except at $p$.

homotopy type of complement of subspace arrangement

2010-03-19T14:25:23Z

I am studying the homotopy type of a space,and i hope it would be a $K(\pi,1)$ space. now i have find its covering,once we can say the covering is $K(\pi,1)$,so is the space itself.and the covering is

$R^4-M$ where $M=M_1\cup M_2\cup M_3\cup M_4$,

$M_1=\{(x,y,z,w)|x,y \in \mathbb R,z,w \in\mathbb Z\}$

$M_2=\{(x,y,z,w)|y,z \in \mathbb R,x,w \in\mathbb Z\}$

$M_3=\{(x,y,z,w)|x,w \in \mathbb R,y,z \in\mathbb Z\}$

$M_4=\{(x,y,z,w)|z,w \in \mathbb R,x,y \in\mathbb Z\}$

I guess $R^4-M$ is $K(\pi,1)$ space,can someone help prove this?

Montague's Reflection Principle and Compactness Theorem

2010-03-19T19:41:20Z

Here's a question I can't answer by myself: The Reflection Principle in Set Theory states for each formula $\phi(v_{1},...,v_{n})$ and for each set M there exists a set N which extends M such that the following holds

$\phi^{N} (x_{1},...,x_{n})$ iff $\phi (x_{1},...,x_{n})$ for all $x_{1},...x_{n} \in N$

Thus if $\sigma$ is a true sentence then the RFP yields a model of it and as a consequence any finite set of axioms of ZFC has a model (as a consequence ZFC is not finitely axiomatizable by Gödel's Second Incompleteness Theorem)

But why can't I just use now the Compactness Theorem (stating that each infinte set of formulas such that each finite subset has a model, has a model itself) to obtain a model of ZFC (which is actually impossible)??

Ubiquity of the push-pull formula

2010-03-19T22:09:08Z

The push-pull formula appears in several different incarnations. There are, at least, the following:

1) If $f \colon X \to Y$ is a continous map, then for sheaves $\mathcal{F}$ on $X$ and $\mathcal{G}$ on $Y$ we have $f_{*} (\mathcal{F} \otimes f^{*} \mathcal{G}) \cong f_{*} (\mathcal{F}) \otimes \mathcal{G}$ .

A similar formula holds for the derived functors and for $f^{!}$.

2) If $f \colon X \to Y$ is a proper map of schemes, with $Y$ smooth, both $f^{*}$ and $f_{*}$ are defined, and $f_{*}(\alpha \cdot f^{*} \beta) = f_{*} \alpha \cdot \beta$ .

Of course a similar results holds if $f$ is a proper map of smooth manifolds, using Gysyn map for push-forward.

3) If $H < G$ are finite groups, we have two functors $\mathop{Ind}_{H}^{G}$ and $\mathop{Res}_{H}^{G}$ , which can be seen as pull-back and push-forward maps between the representations rings $R(G)$ and $R(H)$. Again we have $\mathop{Ind}(U \otimes \mathop{Res} V) \cong \mathop{Ind} U \otimes V$ .

There are probably several other variations which now I fail to recall. I should mention that in some situations 2) can be obtained by 1), but not always, as far as I know.

Is there a unifying principle (even informal) which explains why in these diverse settings we should always have the same formula?

How to start Game theory?

2010-03-19T20:42:40Z

Hi everybody,

I recently got interested in Game Theory but I don't know where should I start. Can anyone recommend any references and textbooks? And what are the prerequisites of Game Thoery?

Thanks in advance.

Finding the local/global minima of Shubert function

2010-03-19T15:04:17Z

Consider the 2D Shubert function. As given in that page, the function has 18 global minima and several local minima. How can I find the (x,y) of all these minima? Any help appreciated. If it was a summation (instead of a product), I would have done it by minimizing each individual term. However, I have 0 clue as to how to find the minima in this case.

UPDATE: Before applying any global optimizer, I want to know "theoretically" what are the (x,y) of all the minima. I want to be able to compare the expected and the obtained results

Does the Baker-Campbell-Hausdorff formula hold for vector fields on a (compact) manifold?

2010-03-19T14:43:13Z

Consider a compact manifold M. For a vector field X on M, let $\phi_X$ denote the diffeomorphism of M given by the time 1 flow of X.

If X and Y are two vector fields, is $\phi_X \circ \phi_Y$ necessarily of the form $\phi_Z$ for some vector field Z?

Since $X\mapsto \phi_X$ can be thought of as the exponential map from the Lie algebra of vector fields to the group of diffeomorphisms, an obvious candidate is that Z should be given by the Baker-Campbell-Hausdorff formula $B(X, Y) = X+Y+\frac{1}{2}[X,Y]+\cdots$. But does this hold in this infinite-dimensional setting? If so, in which sense does the series converge to Z?

Also, I'm interested in the case where M is a symplectic manifold and we consider only symplectic vector fields (ie. vector fields for which the contraction with the symplectic form is a closed 1-form). Locally, X and Y are the Hamiltonian vector fields associated to smooth functions f and g, so I assume that asking whether B(X, Y) makes sense/is symplectic corresponds to asking whether B(f, g) makes sense/defines a smooth function (where, of course, we use the Poisson bracket in the expansion of B(f, g)). The right-hand side of B(f,g) consists of lots of iterated directional derivatives of f and g in the X_f and X_g directions; it is not clear to me that the coefficients in the BCH formula make the series converge (uniformly, say) for any choice of f and g.

additive structure in a small multiplicative group of a finite field?

2010-03-19T19:08:29Z

Let $p$ be a prime. Given a positive integer $n$, does there exist a $\beta$ in an extension of $F_p$ such that

1) If $F_p[\beta] = F_{p^N}$, then $N > n^n$; ( $\beta$ lies in a high extension)

2) The order of $\beta$ is at most $2^{poly(n)}$; ( $\beta$ has small order)

3) $\beta F_p + \beta^n F_p + \beta^{n^2} F_p + ... + \beta^{n^n} F_p \subseteq < \beta > $; (the subgroup generated by $\beta$ contains a linear space )

Thanks,

Are combinatorial configurations whose Levi graphs may be represented as covering graphs over voltage graphs realizable with pseudolines?

2010-03-19T22:04:37Z

This question is related to this previous question. Many combinatorial configurations have Levi graphs which may be represented as derived graphs obtained from voltage graphs over a cyclic group; in a number of such cases, it is possible to represent the combinatorial configuration as a geometric configuration (i.e., using points and straight lines in the Euclidean plane).

Given a bipartite graph which is obtained from a voltage graph, we can view it as a Levi graph of some combinatorial configuration. Is it possible to draw all such configurations using pseudolines? If not, are there easy/known constraints on the ones that fail? (e.g., if there are more than x points in the configuration, then things work? You can't use such-and-so groups as the cyclic group for the voltage graph?)

(Does the Heawood graph have a voltage-graph representation? If so, it makes the first question easy to answer, but the second one is still interesting. Maybe.)

Existence of Fermi coordinates on a Riemannian manifold

2010-03-19T01:39:40Z

Let $(M,g)$ be a Riemannian manifold, $p$ a point on the manifold and $v \in T_p M$. Let $\gamma$ be the geodesic starting at $p$ in the direction $v$. There exists a time $t_f$ such that there exists a Fermi coordinate system adapted to $\gamma$ up to time $t_f$.

My question: Does there exist a lower bound for $t_f$ in terms of the 2-jet of $g$ at $p$?

That is, I have solid estimates on $g$ up to its second derivatives at $p$: $$\|g\| + \|\nabla g\| + \|\nabla^2 g\| \le h \qquad (1)$$ for some $h$. I would like to show that there exists $f(h)$ such that $$t_f \ge f(h)$$ for all Riemannian metrics satisfying (1) at $p$.

Edit (Mar 19): Taking the helpful advice of Anton, Deane, TK and Willie into account, I've reworded the question:

Let $U = B(0,r)$ be the closed Euclidean ball of radius $r$ in $\mathbb R^n$. Write $$\lambda = \inf_{x \in U} \inf_{\|v\|=1} \langle v,v \rangle_{g(x)}$$ as the minimum eigenvalue of the metric in $U$, and suppose that $$\frac{1}{\lambda} + \|g\|_{C^2(U)} \le h.$$ This is a more refined version of (1) above. Since $$\ddot \gamma^k = -\Gamma^k_{ij} \dot \gamma^i \dot \gamma^j,$$ our estimate gives a control on the acceleration of a geodesic $\gamma$ in $U$, so there exists a minimum self-intersection time $t_i$ depending on $h$ and $r$ (i.e., if $t, t' \le t_i$ then $\gamma(t) \ne \gamma(t')$).

Does this imply the existence of a uniform lower bound on $t_f$ (depending only on $r$ and $h$)? If so, can we relax the control on the second derivative of $g$?

More succinctly: Are existence and non-self-intersection of a geodesic the only obstructions to the existence of Fermi coordinates?

Strengthening of Dirichlet's theorem on arithmetic progressions

2010-03-05T05:52:30Z

Hello all, Dirichlet's famous theorem asserts that any arithmetic progression $\lbrace ax+b | x \in {\mathbb N}\rbrace$ contains infinitely many primes if a and b are relatively prime.

I am wondering if the following strengthening of Dirichlet's theorem is also true :

Let $a,b$ be relatively prime integers as above. Then there is a uniform bound $g(a,b)$ such that any interval $\lbrace x+1,x+2, \ldots ,x+g(a,b)\rbrace$ of $g(a,b)$ successive integers contains at least one integer $y$ which is congruent to $b$ modulo $a$ and which is not divisible by any integer between $x+1$ (inclusive if $y\neq x+1$) and $y$ (exclusive).

Without the uniform bound, this would be a tasteless easy consequence of Dirichlet's theorem. With the bound, however, it becomes stronger than Dirichlet's theorem.

Perhaps the two are in fact equivalent ?

Is there a good reference for the relationship between the Yangian and formal based loop group?

2010-03-19T20:21:21Z

For every finite dimensional semi-simple Lie group $\mathfrak{g}$, we have a loop algebra $\mathfrak{g}[t,t^{-1}]$. This loop algebra has a natural invariant inner product by taking the residue at zero of the Killing form applied to two elements (i.e. $t^k\mathfrak{g}$ and $t^{-k-1}\mathfrak{g}$ are paired by the Killing form.)

This Lie algebra actually has a Manin triple structure with respect to this inner product: the subalgebras $\mathfrak{g}[t]$ and $t^{-1}\mathfrak{g}[t^{-1}]$ are both isotropic, and non-degenerately paired by this form. This makes $\mathfrak{g}[t]$ into a Lie bialgebra, by getting the cobracket from the bracket on $t^{-1}\mathfrak{g}[t^{-1}]$.

Now, as we all know, Lie bialgebras can be quantized: in this case, the result is a quite popular Hopf algebra called the Yangian. By the usual yoga of quantization of Lie bialgebras, the dual Hopf algebra to the Yangian quantizes the universal enveloping $t^{-1}\mathfrak{g}[t^{-1}]$, so if you take a different associated graded of the Yangian, you must get the Hopf algebra of functions on the group with Lie algebra $t^{-1}\mathfrak{g}[t^{-1}]$, which is $L_<G$ , the based formal loop group.

Now, all of these things also have explicit descriptions in terms of equations, and it seems as though this story must be worked out explicitly somewhere, but I've had little luck locating it. Does anyone know where? Or is this story just wrong, and that's why I can't find it?

Occurrence of the trivial representation in restrictions of Lie group representations

2010-03-19T16:42:16Z

Suppose $G$ is a semisimple group, and $V_{\lambda}$ is an irreducible finite-dimensional representation of highest weight $\lambda$. Suppose $H \subset G$ is a semisimple subgroup. What is the multiplicity of the trivial representation in $V_{\lambda}|_{H}$? Is there a simple way to read this off from $\lambda$ and the Dynkin diagrams of $G$ and $H$?

transcendental Galois theory

2010-01-16T04:40:18Z

Suppose we define an arbitrary field extension $K/F$ to be Galois if, for all subextensions $L$ of $K/F$, we have $K^{\operatorname{Aut}(K/L)} = L$. In words: for any element $x$ of $K \setminus L$, there exists an automorphism $s$ of $K$ such that $s(l) = l$ for all $l$ in $L$, but $s(x) \neq x$. (Note that in case $K/F$ is algebraic, this is indeed a characteristic property of Galois extensions.) What are the transcendental Galois extensions?

In my rough notes Transcendental Galois Theory, I show that if $F$ has characteristic $0$ and $K$ is algebraically closed, then $K/F$ is Galois in the above sense. [Actually, these notes are somewhat incomplete. Having been unable to complete the proof of the conjecture below, I left out some of the more straightforward details. If anyone wants to see more detail on anything in these notes, please let me know.]

I also conjectured: if $K/F$ is Galois, then either $K/F$ is algebraic, normal and separable, or $F$ has characteristic $0$ and $K$ is algebraically closed. Is this true?

Comment: It is easy to see that if $K/F$ is not algebraic, then $K$ must have characteristic $0$. It is possible to modify the question a bit so that the positive characteristic case is not ruled out, but I would like to understand what's going on in characteristic $0$ first!

In my notes, I show that an affirmative answer follows from a certain (arguably) less weird conjecture about Galois closures of subfields of rational function fields. If there is any interest, I will reproduce this conjecture here explicitly.

Does a locally free sheaf over a product pushforward to a locally free sheaf?

2010-03-16T17:43:52Z

Suppose $X$ and $Y$ are two (smooth, affine) algebraic varieties. Let $\mathcal{F}$ be a locally free coherent sheaf over $X \times Y$, and let $\mathcal{G}$ be the pushforward of $\mathcal{F}$ to $X$. Is it true that $\mathcal{G}$ is a locally free quasicoherent sheaf?

Sylow Subgroups

2010-03-19T05:15:31Z

I had been looking lately at Sylow subgroups of some specific groups and it got me to wondering about why Sylow subgroups exist. I'm very familiar with the proof of the theorems (something that everyone learns at the beginning of their abstract algebra course) -- incidentally my favorite proof is the one by Wielandt -- but the statement of the three Sylow theorems still seems somewhat miraculous. What got Sylow to imagine that they were true (especially the first -- the existence of a sylow subgroup)? Even the simpler case of Cauchy's theorem about the existence of an element of order $p$ in a finite subgroup whose order is a multiple of $p$ although easy to prove (with the right trick) also seems a bit amazing. I believe that sometimes the hardest part of a proving a theorem is believing that it might be true. So what can buttress the belief for the existence of Sylow subgroups?

univariate prior corresponding to weighted sum of L1 and L2 penalties?

2010-01-20T16:07:48Z

Is there a univariate probability distribution $p_{\lambda,\alpha}(\beta)$ over the reals, parameterized by $\lambda > 0$ and $1 >= \alpha >= 0$, such that $p_{\lambda,\alpha} \propto \exp(-\lambda(\alpha \beta^{2} + (1 - \alpha)|\beta|)$? If so, is it a proper distribution (integrates to 1 over the real line)? Does the density function have a closed form expression? If not, does the density function have some other nice representation?

Background: One approach to avoiding overfitting in regression modeling with many predictors is to minimize the sum of prediction error plus a penalty based on the size of the coefficients. This is particularly used in machine learning problems with large numbers of features, as in computational linguistics and information retrieval. If an L2 penalty (i.e. a penalty proportional to the square of the coefficient) is used this is called ridge regression. It is equivalent to finding the Bayesian maximum a posteriori (MAP) fit with a prior that is the product of univariate gaussian distributions with mean 0. If an L1 penalty (proportion to absolute value of coefficient) is used this is called lasso regression, and is equivalent to finding the Bayesian MAP fit under a prior which is a product of univariate Laplace (double exponential) distributions with mean 0. This paper:

 Zou, Hui and Trevor Hastie. 2005. Regularization and Variable Selection via the Elastic Net. Journal of the Royal Statistical Society B. 67(Part 2):301–320.

introduced the "elastic net" which is a weighted combination of L1 and L2 penalties. My question is whether the elastic net corresponds to MAP estimation under a prior which is a product of univariate distributions, and if so what the nature of that distribution is.

Finding all paths on undirected graph

2010-03-18T15:31:12Z

I have an undirected, unweighted graph, and I'm trying to come up with an algorithm that, given 2 unique nodes on the graph, will find all paths connecting the two nodes, not including cycles. Here's an illustration of what I'd like to do: Graph example

Does this algorithm have a name? Can it be done in polynomial time?

Thanks,

Jesse

Triangles, squares, and discontinuous complex functions

2010-03-19T17:09:34Z

Is there some onto function $f:$ $\mathbb{C}$ $\rightarrow$ $\mathbb{C}$ such that for each triangle $T$ (with its interior), $f(T)$ is a square (with interior, too) ? I would have the same question for triangles and squares without interior, respectively.

How to generate correlated random binary data

2010-03-19T19:04:24Z

Suppose I have a column of random binary numbers. I would like to find a way to generate a second column with the same number of cases that has a specified correlation with the initial column.

Any algorithms or even software to help accomplish this?

How to write IF...ELSE as mathematic equation?

2010-03-19T01:13:16Z

I'm writing a computer program and I need to fit some IF..ELSE condition into mathematic model, so I can't use regular programming constructs. For example, how would I turn this into mathematic equation (or inequation):

if (3ax + 5by + 8cz >= 320) then
    w = 1.0;
else
    w = 0.8;

I understand how to express the domain of w to accept only values 0.8 and 1.0 by using:

(w - 1.0) * (w - 0.8) = 0

But I haven't got a clue how to transform the above IF statement. Is it even possible?

P.S. I'm rather new to math overflow, so I'm not sure which tags to assign to this question. Please feel free to re-tag appropriately.

Is there a sensible notion of abstract constructible space?

2010-03-19T17:59:44Z

In the past by the term "variety" people understood a subset of projective space locally closed for the Zariski topology. Now we have a more natural notion of abstract algebraic variety, i.e. a scheme that is so and so, and we can conceive non quasi-projective varieties.

Now we have the concept of constructible subset of a variety (or of a scheme), i.e. a finite union of locally closed subsets (subschemes). We know that the image of a morphism of varieties may fail to be a subvariety of the target, nevertheless it's always a constructible subset thereof.

Is there a reasonable notion of "abstract constructible space"? And would it be of any utility in algebraic geometry?

Lifting abelian varieties in (the closed fiber) of a fixed Neron model

2010-03-19T16:00:02Z

Suppose that $R$ is a dvr with field of fractions $K$ and residue field $k$ and that $A_K$ is an abelian variety over $K$ with Neron model $A$ over $R$. Then the closed fiber $A_k$ is a smooth commutative group scheme over $k$. Suppose now that $B_k$ is an abelian variety over $k$ that is a quotient of $A_k$.

Does there exist an abelian scheme $B$ over $R$ and a morphism $A\rightarrow B$ of smooth commutative $R$-groups whose base change to $k$ is the quotient mapping $A_k \rightarrow B_k$?

The answer is NO, I'm fairly sure, as the generic fiber of $A$ could be simple with $A_k$ an extension of an abelian variety by a torus. Let us therefore assume that $B_k$ can be lifted up to isogeny, i.e. that there exists $C$ an abelian scheme over $R$ such that 1) $C_k$ is isogenous to $B_k$ and 2) There exists a map of smooth groups $A\rightarrow C$ over $R$ whose base change to $k$ is the quotient map $A_k\rightarrow B_k$ followed by the isogeny $B_k\rightarrow C_k$. With this added assumption, is the answer to the question above still NO?

I'm inclined to think that this is the case, but can't immediately convince myself of this.

Is there a name for this property of a topology?

2010-03-19T16:34:22Z

This property seems like it should have a nice name, but I can't find one anywhere. Does anyone know a name for this?

For each non-empty open set $U$, there exist proper open subsets $\{U_i\}_{i\in I}$ such that $U=\cup_i U_i$.

I suppose this could also be formulated as each nonempty open set having an open cover of proper subsets, or being the colimit of its open subsets.

(Also, apologies if this is something obvious I should have thought of.)

Fox Calculus and Cohomology.

2010-03-19T13:57:54Z

Good day,

Could someone please give a reference about how to use Fox Calculus to compute the cohomology of a $2$-group $G$ with coefficients in a submodule of $\oplus^n F_2[G]$.

Is there a formula to count Fox derivations? $G\to F_2[G]$.

Thanks.

tangent bundle and orientation

2010-03-19T17:14:41Z

Let M is a smooth manifold, TM is tangent bundle. We know TM is Manifold too. How to make TM orientable?

Integer points (very naive question)

2010-03-19T14:00:22Z

Well, I don't have any notion of arithmetic geometry, but I would like to understand what arithmetic geometers mean when they say "integer point of a variety/scheme $X$" (like e.g. in "integer points of an elliptic curve").

Is an integer point just defined as a morphism from $Spec\mathbb{Z}$ into $X$?

Suppose $X$ is given a structure of variety over, say, $Spec\mathbb{C}$; does the notion of integer point interact with this structure?

How is all of this related to finding the integer solutions of a concrete polynomial equation (perhaps with integer coefficients)?

Now a very, very, naif question. Suppose you have the plane $\mathbb{A}^{2}_{\mathbb{C}}$ and draw two lines on it: $X={x=0}$ and $X'={x=\pi}$ (with the obvious reduced induced closed subscheme structure). Well, $X$ and $X'$ are clearly isomorphic as schemes over $\mathbb{C}$ (hence as schemes). But, if having integer points is somehow related to finding integer solutions to equations, how do you explain that $X$ (as embedded in $\mathbb{A}^{2}$) has plenty of points with integer coordinates, while $X'$ has none? This to mean: how can the intrinsic notion of a morphism from $Spec\mathbb{Z}$ be possibly related to finding solutions to concrete (coordinate dependent) equations?

Reductive subgroup corresponding to a subdiagram of the Dynkin diagram of a simple group

2010-03-19T15:52:20Z

I am looking for a reference for the following well-known fact: For any subdiagram $\Delta_0$ of of the Dynkin diagram $\Delta=D(G)$ of an adjoint simple group $G$ over an algebraically closed field $k$, there exists a reductive subgroup of maximal rank $G_0\subset G$ with Dynkin diagram $\Delta_0$.

To be more precise, I am looking for a reference for a proof of the following well-known lemma:

Lemma 1. Let $G$ be an adjoint, connected, simple algebraic group with Dynkin diagram $\Delta=D(G)$ over an algebraically closed field $k$ of any characteristic. Let $\Delta_0$ be a subdiagram of $\Delta$ (that is, a subset $\Pi_0$ of the set $\Pi$ of vertices of $\Delta$, together with all the edges of $\Delta$ connecting pairs of vertices of $\Pi_0$). Then there exists a connected reductive $k$-subgroup of maximal rank $G_0$ of $G$ such that the corresponding adjoint semisimple group $G_0^{ad}$ has Dynkin diagram $\Delta_0$.

I know a simple proof of Lemma 1, but I would prefer to give a reference rather than a proof.

The proof goes as follows. Let $T$ be a maximal torus of $G$, and let $R=R(G,T)$ be the root system, then our $\Pi$ is a basis of $R$. Let $S$ be the subgroup of $T$ orthogonal to $\Pi_0$, then it is a subtorus of $T$ (because $G$ is adjoint). Set $G_0=C_G(S)$, the centralizer of $S$ in $G$. Then $G_0$ is a connected reductive subgroup of $G$. It is easy to see that (the adjoint group of) $G_0$ has Dynkin diagram $\Delta_0$.

Note that Lemma 1 is a special case of the following Lemma 2, for which I would also be happy to have a reference.

Lemma 2. Let $G$ be an adjoint, connected, simple algebraic group over an algebraically closed field $k$ of any characteristic. Let $T$ be a maximal torus of $G$, and let $R=R(G,T)$ be the root system. Let $R_0$ be a closed symmetric subset of $R$. Then there exists a connected reductive $k$-subgroup of maximal rank $G_0$ of $G$ with root system $R_0$.

I will be grateful to any references, comments, etc. (also to a proof of Lemma 2).

Mikhail Borovoi

is there a name for this type of function ?

2010-03-19T11:33:40Z

imagine you have a function f() which receives n parameters and it produces one result.

imagine that you then want to compute f for the same n parameters and another one. if you had kept the previous result the operation would be straight forward and constant in terms of cost.

For example imagine you have the function sum() if I ask sum(1,2,5,4) the answer is 10.

I then ask sum(1,2,5,4 and 3) the answer is 13. but this could be achieved also by 10 + 3 (10 being the previous result)

I want to know if there is a scientific name for the class of functions whose value can be determined by previous input.

I have this problem where if we compute a result for a certain function and then we want to do the same thing and adding a new parameter we still have to recompute everything. That's because this function (differently from sum or average or many others would not belong to this class)

is there any name for this ?

hope I have made myself clear.

Google question: In a country in which people only want boys

2010-03-12T09:02:44Z

Hi all!

Google published recently questions that are asked to candidates on interviews. One of them caused very very hot debates in our company and we're unsure where the truth is. The question is:

In a country in which people only want boys every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

Despite that the official answer is 50/50 I feel that something wrong with it. Starting to solve the problem for myself I got that part of girls can be calculated with following series:

$$\sum_{n=1}^{\infty}\frac{1}{2^n}\left (1-\frac{1}{n+1}\right )$$

This leads to an answer: there will be ~61% of girls.

The official solution is:

This one caused quite the debate, but we figured it out following these steps:

Imagine you have 10 couples who have 10 babies. 5 will be girls. 5 will be boys. (Total babies made: 10, with 5 boys and 5 girls)

The 5 couples who had girls will have 5 babies. Half (2.5) will be girls. Half (2.5) will be boys. Add 2.5 boys to the 5 already born and 2.5 girls to the 5 already born. (Total babies made: 15, with 7.5 boys and 7.5 girls.)

The 2.5 couples that had girls will have 2.5 babies. Half (1.25) will be boys and half (1.25) will be girls. Add 1.25 boys to the 7.5 boys already born and 1.25 girls to the 7.5 already born. (Total babies: 17.5 with 8.75 boys and 8.75 girls).

And so on, maintianing a 50/50 population.

Where the truth is?

Top Questions - MathOverflow