Remarks on the Zeros of the Associated Legendre Functions with Integral Degree

Chapter 1. Introduction to Artificial Intelligence一.填空题1. Each rule in production system is written in the form( )2. In production system, the action of the first rule whose condition evaluatesto（）is executed.3. This network can represent the function（）4. This network can represent the function （）5. If the sensory input for the boundary-following robot consists of the valuesof s1…s8, then there are （）different combinations of theses values.6. An action may cause a change in the organism’s perception, which can lead toa different type of action. We call this the （）cycle.7. TLUs can only realize （）separable functions.8. By varying the weights and the threshold, we can realize any ()of the input space into a region that yields output 1, and another region that yields output 0.9. By varying the weights and the ( ), we can realize any linear se paration of the input space into a region that yields output 1, and another region that yields output 0.10. By varying the ( ) and the threshold, we can realize any linear separation of the input space into a region that yields output 1, and another re gion that yields output 0.解答:1.2.3.4.5.6.7.8.9.10.二.判断题1. A computer with a trillion terabytes of memory capable of a trillion teraflops would be smarter than a human being2. The human brain can be described, to a first approximation, as a very large m ultilayer feedforward neural network3. A system must think like a human in order to pass the Turing Test reliably.4. Exact machine translation is available now.5. AI, broadly defined, is concerned with intelligence behavior in artifacts.6. AI is the study of intelligence independent of its embodiment in humans, anim als or machines7. AI is the study of how to do things which at the moment people do better8. AI is the science of making machines do things that would require intelligence if done by men.9. AI is the pursuit of metaphysics by other means.10. AI is the use of computer programs and programming techniques to cast light on the principles of intelligence in general and human thought in particular解答:1.2.3.4.5.6.7.8.9.10.三.名词解释1. Aritficial2. ANN3. Turing test4. Chinese room5. Dartmouth Conference6. Deep Blue7. Expert Systems8. Machine Learning9. DAI10. Pattern Recognition解答:1.2.3.4.5.6.7.8.9.10.四.应用题解答:Chapter 2. Stimulus-Response Agent一.填空题1. Each rule in production system is written in the form ()2. In production system, the action of the first rule whose condition evaluatesto（）is executed.3. This network can represent the function（）4. This network can represent the function （）5. If the sensory input for the boundary-following robot consists of the valuesof s1…s8, then there are （）different combinations of theses values.6. An action may cause a change in the organism’s perception, which can lead toa different type of action. We call this the （）cycle.7. TLUs can only realize （）separable functions.8. By varying the weights and the threshold, we can realize any ()of the input space into a region that yields output 1, and another region th at yields output 0.9. By varying the weights and the ( ), we can realize any linear se paration of the input space into a region that yields output 1, and another regi on that yields output 0.10. By varying the ( ) and the threshold, we can realize any linear separation of the input space into a region that yields output 1, and another re gion that yields output 0.解答:1.2.3.4.5.6.7.8.9.10.二.判断题1. Complex organisms do not just perceive and act, but they also have an interna l state that changes based on the success of previous perception-action cycles a nd this is the mechanism of learning2. Production systems are a standardized way to represent action functions.3. A production system consists of an ordered list of production rules4. In a production system, the action of the first rule whose condition evaluates to 1 is executed.5. Production systems cannot be implemented as electronic circuits.6. By varying the weights and the threshold, we can realize any linear separation of the input space into a region that yields output 1, and another region that yields output 0.7. The procedure of an agent gathers information about its environment is percep tion.8. we can design a TLU to realize the XOR function9. In order to realize XOR with TLUs, we need to combine multiple TLUs into a ne twork.10. TLUs can only realize linearly separable functions.解答:1.2.3.4.5.6.7.8.9.10.三.名词解释1. Production system2. TLU3. Linear Separability解答:1.2.3.四.应用题解答:Chapter 3. Uninformed Search一.填空题1. Many problems have search spaces so large that they cannot be represented by ( ) graphs.2. For eight-puzzle problem, the number of nodes in the state-space graph is ()3. In principle, it is ( ) (possible/impossible) to transform an impl icit representation of a graph into an explicit one.4. to transform an implicit representation of a graph into an explicit one, you need generates all of the nodes that are ( )of the start node (by applying all operators at that node), then generates all of their successors, andso on.5. ( ) requires the construction and memorization of almo st the complete search tree.6. ( ) requires the memorization of only the current path and the branches from this path that were already visited.7. ( ) may search unnecessarily deep for a shallow goal.8. ( ) is an interesting combination of breadth-first and depth-first strategies9. ( ) and iterative deepening are guaranteed to find the shortest path to a solution.10. ( ) and breadth-first search are guaranteed to find the shortest path to a solution.解答:1.2.3.4.5.6.7.8.9.10.二.判断题1. Breadth-first search is complete even if zero step-costs are allowed.2. Search algorithms cannot be applied in completely unobservable environments.3. Breadth-first search is complete if the state space has infinite depth but finite branching factor.4. Breadth-first is an optimal search algorithm.5. Breadth-first search finds the nearest solution, where distance measures the number of operations.6. The sequence of operators along a path from start to a goal is called a plan.7. A decision tree is a special case of a state-space graph.8. Decision trees can be used to model problems in which a series of decisions l eads to a solution.9. We can solve all problems by constructing the complete decision tree and then find a path from its root to a leaf that corresponds to a solution of the probl em.10. Depth-first search can guarantee to find the shortest path to a solution解答:1.2.3.4.5.6.7.8.9.10.三.名词解释1. State space2. State space graph3. Depth first search4. Breadth-first search:5. Uninformed search6. Plan7. decision tree8. Iterative deepening9. Implicit State-Space Graph10. Explicit State-Space Graph解答:1.2.3.4.5.6.7.8.9.10.四.应用题1. SearchConsider the unbounded regular 2D grid state space shown below. The start sta te is the origin (marked) and the goal state is at (x,y).(a) What is the branching factor b in this state space?(b) How many distinct states are there at depth k (for k>0)?(c) Breadth-first seach without repeated state checking expands at most ( ) nodes before terminating.(1) ((4x+y+1-1)/3)-1 (2) 4(x+y)-1 (3) 2(x+y)(x+y+1)-1(d) BFS with repeated-state checking expands up to ( ) nodes before termina ting.(1) ((4x+y+1-1)/3)-1 (2) 4(x+y)-1 (3) 2(x+y)(x+y+1)-1(e) True/false: h = |u-x| + |v-y| is an admissible heuristic for a state at(u,v).(f) True/false: A* search with repeated-state checking using h expands O(x+y) nodes before terminating.(g) True/false: h remains admissible if some links are removed.(h) True/false: h remains admissible if some links are added between nonadjacent states.2. Missionaries and cannibals(15 Points)The missionaries(传教士) and cannibals(食人者) problem is usually stated as f ollows. Three missionaries and three cannibals are on left side of a river, along with a boat that can hold one or two people. Find a way to get everyone to theright side, without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place.We can search in the state spaces of this problem to solve it. So we have todefine the state and the operators firstly. The states and operators are definedas below:State: A state consists of an ordered sequence of three numbers representingthe number of missionaries, cannibals, and boats on the left side of the river.Thus, the start state is (3,3,1) and the goal state is (0,0,0).Operators: We define pij as boating i missionaries and j cannibals from leftside of the river to the right side and qij as boating i missionaries and j cannibals from right side of the river to the left side.Draw the state-space graph of this problem. You do not need to draw any sta tes; just complete the graph that I have given. You may mark the operator pij only beside every edge.(Because operator qij is the same as pij)3. SearchConsider a finite tree of depth d and branching factor b.(A tree consisting of only a root node has depth zero; a tree consisting of a root node and its b su ccessors has depth 1;etc.) Suppose the shallowest goal node is at depth g≤d.1.What is the minimum and maximum number of nodes that might be generated bya depth-first search with depth bound equal to d?2. What is the minimum and maximum number of nodes that might be generated bya breadth-first search?3. What is the minimum and maximum number of nodes that might be generated bya depth-first iterative-deepening search?(Assume that you start with an initialdepth limit of 1 and increment the depth limit by 1 each time no goal is foundwithin the current limit.)4. SearchAssume that 10000 nodes per second can be generated in a breadth-first search. Suppose also that 100 bytes are needed to store each node. What are the memoryand time requirements for a complete breadth-first search of a tree of depth dand branching factor of 5? Show these in a table.(You can use approximate numbers when time is better expressed in hours, days, months, years, etc.)5. SearchYou’re a taxi driver. Your taxi can hold 4 passengers. Passengers pay a flatfee for a ride to the airport, so goal is to pick up 4 passengers and take themto the airport in the smallest number of miles. Your world can be modeled as agraph of locations with distances between them. Some, but not all, of the locations have passengers that you can pick up.a. Describe the state space of this search problem.b. What would be a good cost function for this search problem?c. Now, consider a case where passengers have to pay according to how far away they are from the airport when they’re picked up (note: they don’t pay according to how long a ride they take in your taxi, but according to the length of the shortest path from their pickup-point to the airport). Describe the state space of this search problem.6. SearchAssume we are searching a tree with branching factor b. However we do not know that we are really searching a tree, so we are considering checking each state description generated to see if it matches a previously generated state description. How many such checks would have to be made in a search of the tree to depth d?7. SearchThere are 3 circles labeled with A, B, C. Each circle is labeled with 1, 2, 3, 4 every 90°. Every time you can rotate a circle with 90° anticlockwise. Thestart state and goal state are shown in the figure. Solve it with breadth firstsearch and draw the search tree.8. SearchThere are three match sticks(火柴棒)on the desktop. The head of the middle on e is upright and the other two are downright. Assuming one step is reversing the direction of one stick. After three steps, can you make all the three sticks upright or downright? Draw the state space graph and answer this problem.Hint: a state can be represented as s(x1, x2, x3), xi=0 stands for the stickxi is upright.9. SearchOne farmer, one fox, one chick and rice are on the left side of a river. There is only one boat and the boat can hold two of them one time. Only the farmer c an paddle the boat from one side to the other side of the river. If there is nothe farmer, the fox will eat the chick, and the chick will eat rice. Solve it with breadth first search and draw the search tree.10. SearchThere are four cards on a table. Two of them are black(B) and the other two a re white(W). Assuming that: (i) a card can move to an adjacent and blank cell, (ii) a card can jump over another one to a blank cell. The goal is to move all white cards on the left of the black cards. Draw the state space graph of this pro blem.解答:1.2.3.4.5.6.7.8.9.10.Chapter 4. Uniform Cost Search and Heuristic Search一.填空题1. Nodes in ( ) keep track of total path length from start to that node when uniform cost search is used.2. OPEN kept in priority queue ordered by ( ) when uniform cost se arch is used.3. We examine a node to see if it is the goal only when we ( )(t ake it off/put it in) the OPEN4. The uniform cost search algorithm is optimal only when the costs are ().5. If we simply append new nodes to the end of OPEN, the algorithm turns into ()6. If we simply append new nodes to the star of OPEN, the algorithm turns into ( )7. If we sort the nodes according to a heuristic evalua tion function f’ , the a lgorithm turns into ( ).8. We can often improve search efficiency by implementing a () that estimates which node is the best one to expand in a given situ ation.9. Depth-first, breadth-first and uniform-cost searches are ().10. Depth-first, breadth-first and ( ) searches are uninformed.解答:1.2.3.4.5.6.7.8.9.10.二.判断题1. Assume that a rook can move on a chessboard any number of squares in a straig ht line, vertically or horizontally, but cannot jump over other pieces. Manhattan distance is an admissible heuristic for the problem of moving the rook from sq uare A to square B in the smallest number of moves.2. Depth-first search always expands at least as many nodes as A_ search with an admissible heuristic.3. Assume that a king can move one square in any direction on a chessboard (8 di rections in all). Manhattan distance is then an admissible heuristic for the pro blem of moving the king from square A to square B.4. We can often improve search efficiency by implementing a heuristic evaluation function f’ that estimates whi ch node is the best one to expand in a given sit uation.5. Heuristic evaluation functions have to be “custom-made” for individual prob lems.6. If we use a“stupid”estimation function such as h’(n) = 0, A* is still guaranteed to find a minimal cost path.7. The more closely our function h’(n) is to the actual function h(n), the better will be the efficiency of A* in finding a path.8. Algorithm A* has memory demands that increase exponentially with the depth of the goal node.9. For our heuristic es timation function f’(n) = g’(n) + h’(n), if we simplyset h’(n) = 0, the algorithm will turn into breadth-first search.10. Under any conditions, A* is guaranteed to find the minimal cost path解答:1.2.3.4.5.6.7.8.9.10.三.名词解释1. Heuristic Search2. Algorithm A*3. Admissibility in A*解答:1.2.3.四.应用题1. Eight puzzleThe task is to transform an initial puzzle into a goal state by shifting numb ers up, down, left or right.The initial state is: The goal state is:2 83 1 2 31 6 4 8 47 5 7 6 5(a) What would be a good heuristic function for this search problem?(b) Use your heuristic to carry out an A* search to find a solution. Draw the search tree as you go, showing for each node both the state it represents (incl ude all information needed to distinguish this state from other states) and the node’s f, g, and h.2. Heuristic SearchConsider the problem of moving k knights from k starting squares s1,…,s k to k goal squares g1,…，g k, on an unbounded chessboard, subject to the rule that no two knights can land on the same sq uare at the same time. Each action consists of moving up to k knights simultaneo usly. We would like to complete the maneuver in the smallest number of actions.(a) What is the maximum branching factor b in this state space? ( )(i) 8k (ii) 9k (iii) 8k(iv) 9k(b) Suppose h i i s an admissible heuristic for the problem of moving knight I to goal g i by itself. Which of the following heuristics are admissible for the k-knight problem?( )(i) min{h1,…,h k} (ii) max{h1,…,h_k} (iii) ∑k i=1 h i(c) Which of these is the best heuristic?( )(i) min{h1,…,h k} (ii) max{h1,…,h_k} (iii) ∑k i=1 h i3. Heuristic SearchSuppose you’re trying to solve the following puzzle. The puzzle involves numbers from 100 t o 999. You’re given two numbers called S and G. You’re also given a set of numbers called bad. A move consists of transforming one number intoanother by adding 1 to one of its digits or subtracting 1 from one of its digits; for instance, a move can take you from 678 to 679; or from 234 to 134. Moves are subject to the following constraints:? You cannot add to the digit 9 or subtract from the digit 0. That is to say,no “carries” are allowed and the digits must remain in the range from 0 to 9. ? You cannot make a move which transforms your current number into one of thenumbers in the bad.? You cannot change the same digit twice in two successive moves.Since the numbers have only 3 digits, there are at most 6 possible moves at the start. And since all moves except the first are preceded by another move which uses one of the digits, after the start there are at most 4 possible moves perturn. You solve the puzzle by getting from S to G in the fewest possible moves.You task is to use A* search to find a solution to the puzzle.(a) Briefly list the information needed in the state description (not the node description) in order to apply A* to this problem.(b) Find a heuristic for use with A* search in this problem which is admissible and which does not require extensive mathematical calculation (that is, you should be able to use it in solving the second part of this problem without needing a calculator!). Explain clearly why your heuristic is admissible. Try to finda heuristic which is as powerful as possible while still remaining admissible.(c) Use your heuristic to carry out an A* search to find a solution when S=567, G=777, and bad={666,667}. Draw the search tree as you go, showing for each node both the state it represents (include all information needed to distinguish this state from other states) and the node’s f, g, and h order of expansion (thestart node would be labeled 1, the next node to be expanded would be 2,etc.). Include in your tree all legal successors of each node you expand.Hint: for nodes that tie for best-node-to-expand, it’s probably best to givethe search a slightly “depth-first” character by choosing the node with higher g value.4. Bottle world (Heuristic search)Imagine a world which consists of four beer bottles A, B, C, and D. They canbe arranged in any order from left to right, except that bottle A can never be further to the right than bottle D. For example, ABCD, CBAD, and CADB are possible states of our world, whereas DCBA, CDAB, or BCDA can never occur. The world can be manipulated by the schema swap(x, y), which swaps the bottles in positionsx and y. For example, swap(1, 2) turns state BCAD into CBAD. However, swap(1,2),swap(2,3), and swap(2,4) are the only three available operators.a) Draw the state-space graph of this world. You do not need to draw any bottles; just use four-letter sequences to describe states.b) Assume that your world is in the state ADBC, and the goal state is CBAD. Now we define a estimation function f’(n) = g’(n) + h’(n), f’(n) = number ofoperations already performed + (number of bottles in incorrect position)/2. Please write down the resulting search tree, indicate the order in which nodes were created, and for each node n give the value of f’(n).5. Uniform cost searchConsider the following graph, in which A is the start node and F is the goal node. Assume that nodes are visited at most once.1. In what order does uniform-cost search visit the nodes?2. Let the heuristic function h(n) be the minimum number of arcs between node n and the goal node. Is this an admissible heuristic? Why or Why not?3. In what order does A* search visit the nodes? What are their estimated val ues when they are visited?6. 2L-WaterThere are two bottles named A and B to store water. The volume of A is 4L and B is 3L, either with no scales on it. Our aim is to get 2L water exactly in bottle A through some operations. At each step, we can perform one of the three ope rations: (1) filling up one bottle (2) empty one bottle; (3) dump water from one bottle to another. How can you get 2L exactly in bottle A?Searching in state space of this puzzle will lead to a solution and the best-first search can improve search efficiency. So we have to define the state and the estimation function. The states and estimation function are defined as below: State: A state, (x, y), consists of an ordered sequence of two variables repr esenting the volume of water in bottle A and bottle B. Thus, the start state is(0, 0) and the goal state is (2,0).We define the estimation function as f’(n) = g’(n) + h’(n).g’(n) = number of operations already performed.h’(n) = 2 If 0<x<4 and 0<y<3= 4 if 0<x<4 or 0<y<3=10 if x=0 and y=0 or x=4 and y=3=8 if x=0 and y=3 or x=4 and y=0Please draw the search tree, and for each node n give the value of f’(n).7. Missionaries and cannibals(15 Points)The missionaries(传教士) and cannibals(食人者) problem is usually stated as f ollows. Three missionaries and three cannibals are on left side of a river, along with a boat that can hold one or two people. Find a way to get everyone to theright side, without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place.We can search in the state spaces of this problem to solve it. So we have todefine the state and the operators firstly. The states and operators are definedas below:State: A state, (m,c,b), consists of an ordered sequence of three numbers rep resenting the number of missionaries, cannibals, and boats on the left side of the river. Thus, the start state is (3,3,1) and the goal state is (0,0,0).We define t he estimation function as f’(n) = g’(n) + h’(n).g’(n) = number of operations already performed.h’(n) =m+c-2b Please draw the search tree, and for each node n give the value of f’(n).8. Search with visited List.Below is a graph to be searched (starting at S and ending at G).For each of the searches below, just give a list of node names (state name, length of path) drawn from the tree above. Break ties using alphabetical order.1. Perform a depth-first search. Assume children of a state are ordered in al phabetical order. Show the sequence of nodes that are expanded by the search.2. Perform a best-first without a visited or expanded list. Show the sequen ce of nodes that are expanded by the search.3. Perform a Uniform Cost Search without a visited or expanded list. Show the sequence of nodes that are expanded by the search.9. Uniform cost searchConsider the following graph, in which A is the start node andB is the goal n ode. Assume that nodes are visited at most once.1. In what order does uniform-cost search visit the nodes?2. Let the heuristic function h(n) be the minimum number of arcs between node n and the goal node. Is this an admissible heuristic? Why or Why not?3. In what order does A* search visit the nodes? What are their estimated val ues when they are visited?10. Suppose there are two friends living in different cities on a map. On every t urn, we can move each friend simultaneously to a neighboring city on the map. The amount of time needed to move from city i to neighbor j is equal to the road d istance d(i; j) between the cities, but on each turn the friend that arrives first must wait until the other one arrives (and calls the first on his/her cell phone) before the next turn can begin. We want the two friends to meet as quicklyas possible. Let us formulate this as a search problem.(a) What is the state space? (You will find it helpful to define some formal notation here.)(b) What is the successor function?(c) What is the goal?(d) What is the step cost function?(e) Let SLD(i; j) be the straight-line distance between any two cities i andj. Which, if any, of the following heuristic functions are admissible? (If none, write NONE.)(i) SLD(i; j) (ii) 2 _ SLD(i; j) (iii) SLD(i; j)=2解答:1.2.3.4.5.6.7.8.9.10.Chapter 5. Adversarial Search一.填空题解答:二.判断题1. In a fully observable, turn-taking, zero-sum game between two perfectly ratio nal players, it does not help the first player to know what move the second player will make.2. Alpha-Beta search keeps all explored nodes in memory.3. Some pruning is possible in game trees with chance nodes.4. It is possible to write an exact evaluation function for chess.5. Minimax and alpha-beta can sometimes return different results.6. Search can be stopped below any MIN node having a beta value less than or equ al to the alpha value of any of its MAX ancestors.7. Search can be stopped below any MAX node having an alpha value less than or e qual to the beta value of any of its MIN ancestors.8. Alpha value of MAX node can never decrease.9. Beta value of MIN node can never decrease.10. We can use search algorithms to write “intelligent”programs that play game s against a human opponent.解答:1.2.3.4.5.6.7.8.9.10.三.名词解释1. Minimax procedure2. Alpha-Beta Procedure3. Alpha pruning解答:1.2.3.四.应用题1. Game SearchConsider the game tree shown below. Assume the top node is a max node. The la bels on the arcs are the moves. The numbers in the bottom layer are the values of the different outcomes of the game to the max player.1. What is the value of the game to the max player?2. What first move should the max player make?3. Assuming the max player makes that move, what is the best next move for the min player, assuming that this is the entire game tree?。

a rXiv:alg-ge o m/971011v24Dec1997Canonical rational equivalence of intersections of divisors Andrew Kresch 13December 19970Introduction One way to define an operation in intersection theory is to define a map on the group of algebraic cycles together with a map on the group of rational equivalences which commutes with the boundary operation.Assuming the maps commute with smooth pullback,the extension of the operation to the setting of algebraic stacks is automatic.The goal of the first section of this paper is to present the operation of intersecting with a principal Cartier divisor in this light.We then show how this operation lets us obtain a rational equivalencewhich is fundamental to intersection theory.A one-dimensional family of cycles on an algebraic variety always admits a unique limiting cycle,but a family of cycles over the punctured affine plane may yield different limiting cycles if one approaches the origin from different directions.An important step in the historical development of intersection theory was realizing how to prove that any two such limiting cycles are rationally equivalent.The results of the first section yield,as a corollary,a new,explicit formula for this rational equivalence.Another important rational equivalence in intersection theory is the one that is used to demonstrate commutativity of Gysin maps associated to reg-ularly embedded subschemes.In section2,we exhibit a two-dimensional family of cycles such that the cycles we obtain from specializing in two dif-ferent ways are precisely the ones we need to show to be rationally equivalent to obtain the commutativity result.Our explicit rational equivalence respects smooth pullback,and hence the generalization to stacks is automatic.This simplifies intersection theory on Deligne-Mumford stacks as in[7],where con-struction of such a rational equivalencefills the most difficult section of that important paper.Since our rational equivalence arises by considering families of cycles on a larger total space,we are able to deduce(section3)that the rational equiv-alence is invariant under a certain naturally arising group action.The key observation is that we can manipulate the situation so that the group action extends to the total space.This equivariance result is used,but appears with mistaken proof,in[2],where an important new tool of modern intersection theory—the theory of virtual fundamental classes—is developed.The author would like to thank S.Bloch,W.Fulton,T.Graber,and R. Pandharipande for helpful advice and the organizers and staffof the Mittag-Leffler Institute for hospitality during the1996–97program in algebraic ge-ometry.1Intersection with divisorsIn this section we work exclusively on schemes offinite type over afixed basefield.The term variety denotes integral scheme,and by a subvariety we mean an integral closed subscheme.We denote by Z∗X,W∗X,and A∗X,re-spectively,the group of algebraic cycles,group of rational equivalences,and Chow group of a scheme X.The boundary map W∗X→Z∗X is denoted∂. We refer to[3]for basic definitions and properties from intersection theory. Given a Cartier divisor D we denote by[D]the associated Weil divisor(it is important to note that the notion of Weil divisor makes sense on arbi-trary varieties,[3]§1.2).If X is a variety then we denote by X1the set of subvarieties of codimension1.2Definition1.1.Let X be a variety and let D be a Cartier divisor.Let π: X→X be the normalization map.The support of D,denoted|D|,is defined to beπ( W∈ X1ord Wπ∗D=0W).Remark1.2.This agrees with the na¨ıve notion of support(the union of all subvarieties appearing with nonzero coefficient in[D])when X is normal or when D is effective.Remark1.3.There is yet another notion of support which appears in[3]. There,the support of a divisor is a piece of data that must be specified along with the divisor.Given a Cartier divisor D on a variety X,let Z be any closed subscheme such that away from Z the canonical section of O(D)is well-defined and nonvanishing.Then,[3]defines an intersection operation A k(X)→A k−1(Z).Unfortunately,the support|D|which we have defined is not generally a support in this sense.Hence in the definition below we require that our divisors be specified by defining functions which are regular away from their supports.We shall denote by|D|0the set of irreducible components of|D|.Definition1.4.Let X be a variety.A P-divisor on X is a tuple(U,U′,x) such that(i)U and U′are nonempty open subschemes of X such that U∪U′=X; (ii)x∈k(U)∗;(iii)x|U∩U′∈O∗(U∩U′);and(iv)the data(x∈k(U)∗,1∈k(U′)∗)specifies a Cartier divisor D such that |D|=X\U′.By abuse of terminology,we call D a P-divisor if D is the Cartier divisor associated to a P-divisor as in(iv).Given a P-divisor as above,we call x the local defining function.A P-divisor may be pulled back via a morphism of varieties provided that the image of the morphism is not contained in the support of the underlying Cartier divisor.Examples.(i)Let X be a normal variety.Let x∈k(X)∗specify a principal Cartier divisor D.Then(X,X\|D|,x)is a P-divisor.3(ii)Let X be a variety.Every effective principal Cartier divisor is a P-divisor.(iii)Let X be a variety,and letπ:X→P1be a dominant morphism.Then thefiber ofπover{0}is a P-divisor.The operation of intersecting with a Cartier divisor is generally defined only on the level of rational equivalence classes of cycles.When V⊂|D|, we have D·[V]=c1(O(D)|V)∩[V],and there is generally no way to pick canonically a cycle representing thisfirst Chern class.The exception is when O(D)||D|is trivial,or in our terminology,D is a P-divisor.Then,we may define a cycle-level intersection operation(see[3],Remark2.3).Definition1.5.Let X be a variety,and let D be a P-divisor on X.The cycle-level intersection operationD·−:Z k(X)→Z k−1(|D|)is given byD·[V]= [D|V]if V⊂|D|;0if V⊂|D|.The claim that this map passes to rational equivalence and hence gives an intersection operation D·:A k(X)→A k−1(|D|)is proved in[3],but not in a way that makes it easy to see how D·αis to be rationally equivalent to zero ifαis a cycle that is rationally equivalent to zero.Following the program set out in the introduction,we would like to demonstrate this fact by giving an explicit map on rational equivalences which commutes with the boundary operation.Definition1.6.Let X be a variety,and let D be a P-divisor on X with local defining function x.Say V is a subvariety of X with normalization π: V→V,and suppose y∈k(V)∗.We define the intersection operation on the level of rational equivalencesD·−:W k(X)→W k−1(|D|)byD·y= π∗ W∈|π∗D|0(y ord W x/x ord W y)|W if V⊂|D|;(1)0if V⊂|D|.4Here,π∗:W∗ V→W∗V is pushforward of rational equivalence.Remark1.7.This definition explains why we a require the definition of a P-divisor to include more data than just that of the underlying Cartier divisor. The map(1)actually depends on the choice of defining function.Proposition1.8.Let X be a variety and let D be a P-divisor on X.Then the diagramW k(X)D·W k−1(|D|)∂Z k−1(|D|)commutes.This follows easily fromProposition1.9.Let X be a normal variety and let x and y be rational functions with associated principal Cartier divisors D and E.For V∈X1 set a V=ord V x and b V=ord V y.ThenV∈X1∂(y a V/x b V|V)=0;(2)(3)∂(D·y)=D·(∂y);(4)D·[E]−E·[D]= V∈|D|0∩|E|0∂(y a V/x b V|V).Proof.If we split the sum in(2)into a sum over V∈|D|0and a sum over V∈|D|0we obtain(3).Similarly if we split away the terms with V∈|D|0∩|E|0we obtain(4)from(2).So,for afixed variety X andfixed divisors D and E,the three assertions are equivalent.Now,we get(2)as a consequence of the tame symbol in K-theory,cf.[6]§7,or by the following elementary geometric argument.We quickly reduce to the case where D and E are effective.Then,when D and E meet properly,(4)follows from[3], Theorem2.4,case1.An induction on excess of intersectionε(D,E)=maxa V·b VV∈X15completes the proof:if we denote the normalized blow-up along the ideal (x,y)byσ:X′→X and denote the exceptional divisor by Z then we may writeσ∗D=Z+D′andσ∗E=Z+E′,and now|D′|∩|E′|=∅and max(ε(D′,Z),ε(E′,Z))<ε(D,E)(assuming D and E do not meet prop-erly),cf.[3],Lemma2.4.The result pushes forward.Corollary1.10.Let D and E be P-divisors on a variety X,with respective local defining functions x and y.Letπ: X→X be the normalization map. ThenD·[E]−E·[D]=∂ωwhereω∈W∗(|D|∩|E|)is given byω= V∈|π∗D|0∩|π∗E|0π∗(y ord V x/x ord V y|V).2Application to intersection theory on stacksAll stacks(and schemes)in this section are algebraic stacks of Artin type, [1],[5],which are locally offinite type over the basefield.The notion of P-divsor on a stack makes sense(it is as in Definition1.4with“open sub-scheme”replaced by“open substack,”where by“Cartier divisor”in part(iv) of the definition we mean a global section of the sheaf K∗/O∗for the Zariski topology,and where normalization,order along a substack of codimension1, and support of a Cartier divisor are well defined on stacks because they all respect smooth pullback and hence can be defined locally).Since an Artin stack possesses a smooth cover by a scheme,the operation of intersecting with a P-divisor on a stack comes for free once we know that this operation on schemes commutes with smooth pullback.Also for free we get Corollary 1.10in the setting of stacks:the formation ofωfrom X,D,and E commutes with smooth pullback.Proposition2.1.Let X be a variety,let Y be a scheme,and let f:Y→X be a smooth morphism.Let D be a P-divisor on X.Then f∗◦D·=(f∗D)·◦f∗, both as maps on cycles and as maps on rational equivalences.6We now turn to an application of Corollary1.10to intersection theory on Deligne-Mumford stacks(where a reasonable intersection theory exists, cf.[4],[7]).Central to intersection theory on schemes is the Gysin map corresponding to a regularly embedded subscheme,since the diagonal of a smooth scheme is a regular embedding and this way we obtain an intersection product on smooth schemes.The diagonal morphism for a smooth Deligne-Mumford stack is not generally an embedding,but it is representable and unramified.Lemma2.2.Let f:F→G be a representable morphism of Artin stacks. Then f is unramified if and only if there exists a commutative diagramU g VGsuch that the vertical maps are smooth surjective,g is a closed immersion of schemes,and the induced morphism U→F×G V is´e tale.Proof.This is[7],Lemma1.19.Because this is such a basic fact about properties of morphisms in algebraic geometry,we present an elementary proof in the Appendix.To describe a representable morphism,we use the terminology local im-mersion as a synonym for unramified and call f above a regular local im-mersion if moreover g is a regular embedding of schemes.Since formation of normal cone is of a local nature,an obvious patching construction produces the normal cone C X Y to a local immersion X→Y;the cone is a bundle in case X→Y is a regular local immersion.To get Fulton-MacPherson-style intersection theory on Deligne-Mumford stacks we clearly need to have Gysin maps for regular local immersions.In [7],the author supplies this needed Gysin map by giving a(long,difficult) proof of the stack analogue of[3],Theorem6.4,namelyProposition2.3.Let X→Y and Y′→Y be local immersions of Artin stacks.Then[C X×C Y′Y]=[C C X Y×Y Y′C X Y]in A∗(C X Y×Y C Y′Y).Y C Y′Y7Remark2.4.Though our focus is on applications to intersection theory on Deligne-Mumford stacks,we continue to make use of constructions which behave well locally with respect to smooth pullback,and hence our results are valid in the more general setting of Artin stacks.Remark2.5.Given a stack X which is only locally offinite type over a base field,we must take Z∗X to be the group of locallyfinite formal linear com-binations of integral closed substacks.More intrinsically,Z∗X is the group of global sections of the sheaf for the smooth topology Z∗which associates to a stack offinite type the free abelian group on integral closed substacks. Similarly,W∗X is the group of global sections of sheaf W∗.As always,A∗X is defined to be Z∗X/∂W∗X.The methods of the last section allow us to supply a new,simpler proof of this proposition.Proof.Recall that given a closed immersion X→Y there are associated spacesM X Y=BℓX×{0}Y×P1,M◦X Y=M X Y\BℓX×{0}Y×{0},cf.[3]§5.1.Given a locally closed immersion,say with U is an open sub-scheme of Y and X a closed subscheme of U,then M◦X Y:=M◦X U∐U×A1Y×A1makes sense and is independent of the choice of U.This lets us define M◦F G when F→G is a local immersion of stacks,as follows.Assume we have a diagram as in the statement of Lemma2.2,and set R=U×F U and S=V×G V.There are projections q1,q2:S→G.Defines i:M◦R S→M◦U V(i=1,2)to be the composite M◦R S→M◦U×G V S→M◦U V,where thefirst map is induced by the open immersion R→U×G V and the second,by pullback via q i.Then[M◦R S⇉M◦U V]is the smooth groupoid presentation of a stack which we denote M◦F G.We have,by descent,a morphism M◦F G→P1,which isflat and has as generalfiber a copy of G and as specialfiber the normal cone C F G.In the situation at hand,this construction gives(s×t):M◦X Y×Y M◦Y′Y→P1×P1,8and hence a pair of P-divisors,D(corresponding to s)and E(corresponding to t).We note that(s×t)−1({0}×{0})=C X Y×Y C Y′Y.Since the restriction of s×t to P1×P1\{0}×{0}isflat,we have[D]=[C X Y×Y M◦Y′Y]mod Z∗(C X Y×Y C Y′Y),[E]=[M◦X Y×Y C Y′Y]mod Z∗(C X Y×Y C Y′Y).We examine thefiber of s×t over P1×{0}more closely.Thefiber squarei∗C Y′Y C Y′YYgives rise to a closed immersion f makingM◦i∗CY′YC Y′Y fRemark2.6.The map M◦F G→G associated to a local immersion of stacks is not generally separated,though this should cause the reader no concern,since intersection theory is valid even on non-separated schemes and stacks.In fact, even those operations of[7]which require a so-calledfinite parametrization may be carried out on arbitrary Deligne-Mumford stacks which are offinite type over afield(no such operations show up in this paper).This is so thanks to the proof,[5](10.1),that every Deligne-Mumford stack offinite type over afield possesses afinite parametrization,i.e.,admits afinite surjective map from a scheme.Remark2.7.The reader who wishes greater generality may see easily that all results in this section are valid in the setting of Artin stacks which are locally offinite type over an excellent Dedekind domain.3Equivariance for tangent bundle actionWe continue to work with stacks which are locally offinite type over some basefield.A special case of Proposition2.3is when i:X→Y is a local immersion of smooth Deligne-Mumford stacks.Suppose j:Y′→Y is a local immersion,with Y′an arbitrary Deligne-Mumford stack.Recall that the local immersion j gives rise to a natural group action of j∗T Y on C Y′Y.In short,the action is given locally(say Y is an affine scheme and Y′is the closed subscheme given by the ideal I)by considering the action of T Y|Y′on Spec Sym(I/I2)induced by the map I/I2→Ω1Y and proving([2],Lemma 3.2)that the normal cone Spec I k/I k+1is invariant under the group action.If we let N X Y be the normal bundle to X in Y and denote simply by N its pullback to X′:=X×Y Y′,then C X Y×Y C Y′Y is identified with N×X′i∗C Y′Y.Viewing T Y′as a subbundle of j∗T Y,we have the natural action of T Y′|X′on i∗C Y′Y.This plus the trivial action on N gives an action of T Y′|X′on N×X′i∗C Y′Y.Theorem3.1.The rational equivalence between[C i∗CY′YC Y′Y]and[N×X′C X′Y′]produced in the proof of Proposition2.3is invariant under the action of T Y′|X′on N×X′C X′Y′described above.As a consequence,the rational equivalence descends to a rational equiv-10alence on the stack quotient[N×X′i∗C Y′Y/T Y′|X′].This fact is exploited in[2](Lemma5.9,where the authors invoke the incorrect stronger claim appearing in Proposition3.5that the rational equivalence is equivariant for the bigger group T Y|X′).Proof.The question is local,so we may assume Y is an irreducible scheme, smooth and offinite type over the basefield,X is an smooth irreducible closed subscheme of Y,and Y′is a closed subscheme of Y.If X⊂Y′then the group action is trivial and there is nothing to prove,so we assume the contrary.Lemma3.2.Let Y be a smooth irreducible scheme offinite type over afield k,of dimension n,let X be a smooth irreducible closed subscheme of Y of codimension d,and let Y′be a closed subscheme of Y such that X⊂Y′.Let x be a closed point of Y′∩X.Then,after suitable base change by afinite separable extension of the basefield,and after shrinking Y to a neighborhood of x in Y,there exists an´e tale map f:Y→A n such that X maps into a linear subspace of A n of codimension d and such that Y′→f(Y′)is´e tale.Proof.We may assume x is a k-valued point,and moreover that Y sits in A l with X=A l−d∩Y(for suitable l).We may take x to be the origin of A l.We consider as candidates for f all linear functions mapping theflag A l−d⊂A l into theflag A n−d⊂A n.Those f with f∗:T x,Y→T f(x),A n surjective form an open subscheme U of A nl−dl+d2.Define locally closed subschemes V1and V2of Y×U byV1={(y,f)∈(Y′∩X\{x})×U|f(y)=0}andV2={(y,f)∈(Y′\X)×U|f(y)=0},and let pr2:Y×U→U be projection.A dimension count using the fact that X⊂Y′gives dim(V1)<dim(U)and dim(V2)<dim(U),and hence U\ pr2(V2) is nonempty.Since the rational equivalence of the proof of Proposition2.3commutes with´e tale base change,we are reduced by the Lemma to the case where Y=A n and X=A m(as a linear subspace of A n).Now we need the11Key Observation.Assume Y=A n and Y′is a closed subscheme of Y. Identify T Y,as a group scheme over Y,with the additive group A n.Then there is a group action of A n on M◦Y′Y(which we define to be thefiber of M◦Y′Y→P1over A1)which restricts to the natural action of T Y on C Y′Y.Indeed,we let A n act on Y×A1by(a1,...,a n)·(x1,...,x n,t)=(x1+ta1,...,x n+ta n).By the universal property of blowing up,this extends uniquely to an action of A n on M◦Y′Y.If Y′is given by the ideal(f1,...,f k),and if we view M◦Y′Y as the closure of the graph of(f1/t,...,f k/t):Y×(A1\{0})→A k= Spec k[z1,...,z k],then the action is given coordinatewise bya=(a1,...,a n):z i→z i+(f i(x+t a)−f i(x))/t,so at t=0we recover z i→z i+D a f i(x).This is the natural action of T Y on C Y′Y.Concluding the proof of equivariance,we observe that M◦A m A nfits into thefiber diagramM◦A m A n×A n M◦Y′A n M◦Y′A nM◦{0}A n−m4Appendix:unramified morphismsWe give an elementary algebraic proof of the following fact.Lemma4.1.Let S→T be an unramified morphism of affine schemes which are offinite type over a basefield k.Then there exists a commutative diagram of affine schemesU g VTsuch that the vertical maps are´e tale surjective and such that g is a closed immersion.This fact plus the local nature of the property of being unramified gives us Lemma2.2.Proof.Say S=Spec A,T=Spec B,and f is given algebraically by f∗:B→A.Recall that for f to be unramified means that for every maximal ideal p of A with q=f(p),we have f∗(q)·A p=p A p,and the inducedfield extension B/q→A/p is separable.Case1:The inducedfield extension B/q→A/p is an isomorphism. Then,if x1,...,x n are generators of A as a k-algebra,we may writex i=f∗(t i)+w iwith t i∈B and w i∈p,for each i.Since f is unramified,we havew i=m ij=1f∗(y ij)p ijP ij (x 1,...,x n )=p ij and Q i (x 1,...,x n )=q i .LetV =Spec B [X 1,...,X n ] X 1Q 1−t 1Q 1−m 1 j =1y 1j P 1j ,...,X n Q n −t n Q n −m n j =1y nj P nj ,and define g :S →V by B f ∗→A and X i →x i ,and let ϕ:V →T be given byinclusion of B .Then g is a closed immersion,and by the Jacobian criterion ϕis ´e tale in some neighborhood of g (p ).Case 2:The field extension B/q →A/p is separable.Let k ′be the maximal subfield of A/p which is separable over k ,and make the ´e tale base change Spec k ′→Spec k to get f ′:S ′→T ′.Now S ′has an A/p -valued point which maps to p ∈S ,and since k ′together with B/q generates all of A/p we are now in the situation of Case 1.References[1]M.Artin,Versal deformations and algebraic stacks,Invent.Math.27(1974),165–189.[2]K.Behrend and B.Fantechi,The intrinsic normal cone,Invent.Math.128(1997),45–88.[3]W.Fulton,Intersection Theory ,Springer-Verlag,Berlin,1984.[4]H.Gillet,Intersection theory on algebraic stacks and Q -varieties,J.Pure Appl.Algebra 34(1984),193–240.[5]umon and L.Moret-Bailly,Champs Alg´e briques ,Pr´e publ.math.de l’Universit´e de Paris-Sud,1995.[6] D.Quillen,Higher algebraic K -theory,I,in Algebraic K -theory (Seattle,Wash.,1972),pp.85–147,Lect.Notes in Math.341,Springer-Verlag,Berlin,1973.14[7] A.Vistoli,Intersection theory on algebraic stacks and on their modulispaces,Invent.Math.97(1989),613–670.Department of MathematicsUniversity of Chicago5734S.University AvenueChicago,IL60637kresch@15。

ON THE ZEROS OF POLYNOMIALSWITH RESTRICTED COEFFICIENTSPeter Borwein and Tam´a s Erd´e lyiIt is proved that a polynomial p of the formnp(x)=a j x j,|a0|=1,|a j|≤1,a j∈,j=0√has at most cn)zeros in the strip{z∈:|Im(z)|≤α},and in the sector {z∈:|arg(z)|≤α}.These essentially sharp results improve and generalize several earlier results.1.IntroductionThe study of the location of zeros of polynomials fromF n:=p:p(x)=ni=0a i x i,a i∈{−1,0,1}begins with Bloch and P´o lya[2].They prove that the average number of real zeros of a polynomial from F n is at most c√log nreal zeros.This result,which appears to be thefirst on this subject,shows that polynomials from F n do not behave like unrestricted polynomials.Schur[11]and by different methods Szeg˝o[12]and Erd˝o s and Tur´a n[7]improve the above bound to c√n for the number of real zeros of polynomials from a large class,namely for all polynomials of the formp(x)=nj=0a j x j,|a j|≤1,|a0|=|a n|=1,a j∈C.In this paper we extend this result by proving that a polynomial of the formp(x)=nj=0a j x j,|a j|≤1,|a0|=1,a j∈C,cannot have more than c√n)zeros in the strip{z∈C:|Im(z)|≤α},where c is an absolute constant.Theorems2.1–2.3,our main results,have self contained proofs distinct from those in[6].They sharpen and generalize some results of Amoroso[1],Bombieri and Vaaler[4],and Hua[8],who gave upper bounds for the number of zeros of polynomials with integer coefficients at1.The class F n and various related classes have been studied from a number of points of view.Littlewood’s monograph[9]contains a number of interesting,chal-lenging,and still open problems about polynomials with coefficients from{−1,1}. The distribution of zeros of polynomials with coefficients from{0,1}is studied in [10]by Odlyzko and Poonen.22.New ResultsThroughout the paperD(z0,r):={z∈C:|z−z0|<r}denotes the open disk of the complex plane centered at z0∈C with radius r>0. Theorem2.1.Every polynomial p of the formp(x)=nj=0a j x j,|a0|=1,|a j|≤1,a j∈C,has at most c√n)zeros in the strip{z∈C:|Im(z)|≤α},and in the sector{z∈C:|arg(z)|≤α}. Theorem2.3.Letα∈(0,1).Every polynomial p of the formp(x)=nj=0a j x j,|a0|=1,|a j|≤1,a j∈C,has at most c/αzeros inside any polygon with vertices on the circle{z∈C:|z|=1−α},where the constant c depends only on the number of the vertices of the polygon.The sharpness of Theorem2.1can be seen by the theorem below proved in[6]. Theorem2.A.For every n∈N,there exists a polynomial p n of the form given in Theorem2.1with real coefficients so that p n has a zero at1with multiplicity at least√n −1≥c(nα+√Theorem2.B.For everyα∈(0,1),there exists a polynomial p n of the form given in Theorem2.3with real coefficients so that p n has a zero at1−αwith multiplicity at least 1/α −1.(It can also be arranged that n≤1/α2+2.)As a remark to Theorem2.3we point out that a more or less straightforward application of Jensen’s formula gives that there is an absolute constant c>0such that every polynomial p of the formp(x)=nj=0a j x j,|a0|=1,|a j|≤1,a j∈C,has at most(c/α)log(1/α)zeros in the disk D(0,1−α),α∈(0,1).(An interested reader may view this remark as an exercise.We will not use it,and hence will not present its proof.)A very recent(unpublished)example,suggested by Nazarov, shows that this upper bound for the number of zeros in the disk D(0,1−α)is, up to the absolute constant c>0,best possible.So,in particular,the constant in Theorem2.3cannot be made independent of the number of vertices of the polygon.3.LemmasTo prove our theorems we need some lemmas.Ourfirst lemma states Jensen’s formula.Its proof may be found in most of the complex analysis textbooks. Lemma3.1.Suppose h is a nonnegative integer andf(z)=∞k=hc k(z−z0)k,c h=0is analytic on the closure of the disk D(z0,r)and suppose that the zeros of f in D(z0,r)\{z0}are a1,a2,...,a m,where each zero is listed as many times as its multiplicity.Thenlog|c h|+h log r+mk=1logr2π2πlog|f(z0+re iθ)|dθ.A straightforward calculation gives the next lemma.Lemma3.2.Suppose f is an analytic function on the open unit disk D(0,1)that satisfies the growth condition(1)|f(z)|≤12π 2πlog|f(z0+re iθ)|dθ≤c(r).The next lemma is used in the proof of both Theorems2.1and2.2.4Lemma3.3.There is an absolute constant c1such that every polynomial of theformp(x)=nj=0a j x j,|a0|=1,|a j|≤1,a j∈Chas at most c1(nr+√af [1−a,1],a∈(0,1],for every f analytic on the open unit disk D(0,1)satisfying the growth condition (1)in Lemma3.2.For the sake of completeness we present the proof of Lemma3.4in Section4. Proof of Lemma3.3.Without loss of generality we may assume that z0:=1and n−1/2≤r≤1(the case0<r<n−1/2follows from the case r=n−1/2,and the case r>1is obvious.)Let p be a polynomial of the form given in the lemma. Observe that such a polynomial satisfies the growth condition(1)in Lemma3.4. Choose a point z1∈[1−r,1]such that|p(z1)|≥exp−c3r +m log2≤log|p(z1)|+m log2≤1n).Now observe thatD(1,r)is a subset of D(z1,2r),and the result follows. Lemma3.5.Suppose that p is a polynomial of the formp(x)=nj=0a j x j,|a0|=1,|a j|≤1,a j∈C5Let D(z0,r)⊂D(0,1).Let r∈ 34,1implies that|z0|<13.Let m denote the number of zeros of p in the open disk D(z0,r−δ).Applying Jensen’s formula on D(z0,r)and Lemma3.2,we obtainlog 2r−δ≤log|p(z0)|+m log r2π2πlog|p(z0+re iθ)|dθ≤c(r).As0<r<1and0<δ<r,we havelogr1−(δ/r)≥δ4a and with major axis1−a−13a32.Let E a be the ellipse with foci at1−a and1−a+132,1−a+14aThenmax z∈E a |f(z)|≤maxz∈[1−a,1−a+18z+z−18.The Hadamard Three Circles Theorem is applied with r1:=1,r:=2,and r2:= 4.Corollary4.2.Let E a be as in Corollary4.1.Thenmax z∈E a |f(z)|≤322(1−a)(z+z2).Observe that h(0)=0,and thereare absolute constants c4>0and c5>0such that|h(e it)|≤1−c4t2,−π≤t≤π,and for t∈[−c5a,c5a],h(e it)lies inside the ellipse E a.Now let m:= 2πc5/a +1. Letξ:=exp(2πi/(2m))be thefirst2m th root of unity,and letg(z):=2m−1j=0f(h(ξj z)).Using the Maximum Principle and the properties of h,we obtain|f(0)|2m=|g(0)|≤max|z|=1|g(z)|≤maxz∈E a|f(z)|2m−1k=11(m−1)!4<maxz∈E a|f(z)|2e c7(m−1),and the lemma follows by Corollary4.2.5.Proof of the TheoremsProof of Theorem2.1.It is sufficient to prove the upper bound of the theorem for the number of zeros in a triangle with vertices0,w,and w−1,where|w|=17and Re(w)≥14,r:=3 2.it is sufficient to prove that every polynomial p of the formp(x)=nj=0a j x j,|a0|=1,|a j|≤1,a j∈C,has at most c(nα+√,r:=34,r:=32 impliesα−1≤nα).Proof of Theorem2.3.Without loss of generality we may assume thatα∈(0,1 w,where|w|=1−αand Re(w)≥14e iθ,r:=34e−iθ,r:=3w is covered by the union ofS1and S2.Hence the theorem follows from Lemma3.5.References1. F.Amoroso,Sur le diam`e tre transfini entier d’un intervalle r´e el,Ann.Inst.Fourier,Grenoble40(1990),885–911.2. A.Bloch and G.P´o lya,On the roots of certain algebraic equations,Proc.London Math.Soc.33(1932),102–114.3. F.Beaucoup,P.Borwein,D.Boyd,and C.Pinner,Multiple roots of[-1,1]power series,J.London Math.Soc.(to appear).4. E.Bombieri and J.Vaaler,Polynomials with low height and prescribed vanishing,inAnalytic Number Theory and Diophantine Problems,Birkhauser(1987),53–73.85.P.Borwein and T.Erd´e lyi,Polynomials and Polynomial Inequalities,Springer-Verlag,New York,1995.6.P.Borwein,T.Erd´e lyi,and G.K´o s,Littlewood-type problems on[0,1],manuscript.7.P.Erd˝o s and P.Tur´a n,On the distribution of roots of polynomials,Annals of Math.57(1950),105–119.8.L.K.Hua,Introduction to Number Theory,Springer-Verlag,Berlin Heidelberg,NewYork,1982.9.J.E.Littlewood,Some Problems in Real and Complex Analysis,Heath MathematicalMonographs,Lexington,Massachusetts,1968.10. A.Odlyzko and B.Poonen,Zeros of polynomials with0,1coefficients,Ens.Math.39(1993),317–348.11.I.Schur,Untersuchungen¨u ber algebraische Gleichungen.,Sitz.Preuss.Akad.Wiss.,Phys.-Math.Kl.(1933),403–428.12.G.Szeg˝o,Bemerkungen zu einem Satz von E.Schmidt uber algebraische Gleichungen.,Sitz.Preuss.Akad.Wiss.,Phys.-Math.Kl.(1934),86–98.9。

考研英语（翻译）模拟试卷75(总分：60.00，做题时间：90分钟)一、 Reading Comprehension(总题数：6，分数：60.00)1.Section II Reading Comprehension（分数：10.00）__________________________________________________________________________________________ 解析：2.Part CDirections: Read the following text carefully and then translate the underlined segments into Chinese.（分数：10.00）__________________________________________________________________________________________ 解析：【F1】We're moving; into another era, as the toxic effects of the bubble and its grave consequences spread through the financial system. Just a couple of years ago investors dreamed of 20 percent returns forever. Now surveys show that they're down to a "realistic" 8 percent to 10 percent range. But what if the next few years turn out to be below normal expectations? Martin Barners of the Bank Credit Analyst in Montreal expects future stock returns to average just 4 percent to 6 percent. Sound impossible?【F2】After a much smaller bubble that burst in the mid-1960s Standard & Poor's 5 000 stock average returned 6.9 percent a year(with dividends reinvested)for the following 17 years. Few investors are prepared for that. Right now denial seems to be the attitude of choice."That's typical," says Lori Lucas of Hewitt, the consulting firm. You hate to look at your investments when they're going down. Hewitt tracks 500,000 401(k)accounts every day, and finds that savers are keeping their contributions up. But they're much less inclined to switch their money around. "It's the slot-machine effect," Lucas says, "People get more interested in playing when they think they've got a hot machine—and nothing's hot today. The average investor feels overwhelmed."【F3】 Against all common sense, many savers still shut their eyes to the dangers of owning too much company stock. In big companies last year, a surprising 29 percent of employees held at least three quarters of their 402(k)in their own stock. Younger employees may have no choice. You often have to wait until you're 50 or 55 before you can sell any company stock you get as a matching contribution.【F4】But instead of getting out when they can, old participants have been holding, too. One third of the people 60 and up chose company stock for three quarters of their plan, Hewitt reports. Are they inattentive? Loyal to a fault? Sick? It's as if Lucent, Enron and Xerox never happened. No investor should give his or her total trust to any particular company's stock. And while you're at it, think how you'd be if future stock returns—averaging good years and bad—are as poor as Barnes predicts.【F5】If you ask me, diversified stocks remain good for the long run, with a backup in bonds. But I, too, am figuring on reduced returns. Whata shame. Dear bubble, I'll never forget. It's the end of a grand affair.（分数：10.00）(1).【F1】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：当投资泡沫的毒效及其严重后果在整个金融系统中散开时，我们正在进入另外一个时代。

UNIT 5 Sociology Matters1.Culture is the totality of learned,socially transmitted customs,knowledge,material objects,and behavior.It includes the ideas,values,customs,and artifacts of groups of people.Though culture differ in their customs,artifacts,and languages,they all share certain basic characteristics.Furthermore,cultural characteristics change as cultures develop ,and cultures infuence one another through their technological ,commercial, and artistic achievements.文化是指社会传播学，海关，知识，材料的对象，和行为。

它包括思想，价值观，习俗，和人群的文物。

尽管文化在他们的习俗，文物，和语言不同，但是他们都有一些共同的基本特性。

此外，当文化发展时文化特征也在变化，并且文化通过他们的技术，商业，艺术成就相互影响。

Cultural universals文化共性2.All societies,despite their differences,have developed certain general practices known as cultural universals.Many cultural universals are ,in fact,adaptations to meet essential human needs ,such as people’s need for food ,shelter,and clothing. Anthropologist George murdock compiled a list of cultural that included athletic sports, cooking ,funeral ceremonies,medicine,and sexual restrictions.所有的社会，尽管他们的差别，已经形成了一定的一般做法被称为文化的共性。

外文原文：Alternating CurrentAn alternating current is one which varies in the circuit with time. The value of the current at any given instant of time is the instantaneous value of current, symbolized by i . The instantaneous value of current i is deemed positive for one direction of flow though the cross-section of a conductor, and negative for the opposite direction. The direction of current flow in which instantaneous values are positive is called positive. A current is fully specified, if one knows its instantaneous value as a function of time, i =F(t),and its positive direction.Current whose value recur for equal increments of time are called periodic, and the least increment of time for which this recurrent takes place is called the period T . For a periodic current i = F(t)= F(t+T)Fig.4.1 shows an example of the relationship i = F(t) for a periodic current. The arrow in the diagram indicates the positive direction of current flow. The dotted arrows show the actual direction of current flow at the instants of time when i >0 and i <0. The segments of the curve between points a and b or O and c cover a complete cycle of current alternations over one period.The number of cycle or period per second is the frequency of a periodic current. It is reciprocal of its period.T f /1=It is usually to specify the frequency of any periodic quantity in cycle per second. Thus the frequency of a periodic current will be 1 cycle per second, if its period is second, or 1cycle/sec.A direct current may be regarded as a special case of a periodic current whose period is infinitely long and the frequency is thus zero.The term alternating current is often used in the narrow sense of a periodic current whose constant(direction-current)component is zero, or010=⎰T idt TThe frequencies of alternating current encountered in practice range over wide values. The mains frequency is 50Hz in the Soviet Union and Europe, and 60Hz in the United States. Some industrial processes use frequencies from 10Hz to 9105.2⨯Hz .In radio practice, frequencies up to 10103⨯Hz are employed.The definitions for current just introduced(and, indeed, those that will be introduced shortly) fully apply to periodic voltages, e.m.f.s, magnetic fluxes and any other electrical and magnetic quantities. Some additional remarks are only needed with regard to the sign of alternating voltage and e.m.f.s.An alternating voltage between two point A and B, determined along a specified path 1, periodically changes sign, so that if it is assumed to be positive in the direction from A to B. it will be negative in direction from B to A at the same instant of time. This is why it is important to label which of the two directions is assumed positive. In diagrams, such a direction is labeled either by arrows or subscripts in the symbols forvoltage and is regarded to be the positive reference direction of a voltage(or of an e.m.f.s).Electrical engineering uses the simplest and commonest type of alternating current, the one which varies sinusoidally with time; hence the term a harmonic or a sinusoidal current. The preference for sinusoidal currents is explained modulated by the signal in amplitude, frequency or phase. Periodic non-sinusoidal current may likewise be treated as composed of sinusoidal current at a variety of frequencies occurring simultaneously. This is why thorough of sinusoidal-current circuits is of primary importance.The A.C GeneratorAn A.C generator consists of a stationary part, the stator, and a revolving part, the rotor. As a rule the rotor carries magnetic poles with coils around them. These are the filed coils of the generator ,because they establish a magnetic filed in the machine. They are energized with direct current through slip rings and brushes. The slots of the stator staked up from electrical-sheet steel punchings receive the coils of the stator winding. The stator coils are connected in series, as shown by the fully and dotted lines in the drawing.The e.m.f. induced in a stator conductor is given byBlv E =where B —magnetic induction of the field moving relative to the conductor;l —active length of the conductor;v —speed with which the magnetic field moves relative to the conductor.Since l and v are constant, the induced e.m.f. will vary exactly as B varies. If the induced e.m.f is to be sinusoidal(which is usually sought), the distribution of B around the circumference of the stator should be as close to sinusoidal as practicable.With p pole-pairs on the rotor, the e.m.f. will undergo p cycles of changes every revolution. If the speed of the rotor is revolutions per minutes (r/min), this works out to pn cycles per minute, and the frequency of the induced e.m.f. is ： 60/pn f =For f=50Hz, the rotor of a generator with one pair of poles should run at3000r/min.And with two pole-pairs, at 1500r/min. With speeds like this, rotors are usually fabricated with non-salient piles for greater mechanical strength.High-frequency generators operating at 800 to 8000Hz are all of special designs. Their uses are in the heat-treatment and induction-heating field. Still higher frequencies are generated by valve and semiconductor oscillators.Sinusoidal Current The instantaneous value of a sinusoidal current is given by)2sin(ϕ+∏=t TI i m where m I is the peak value or amplitude of the current, and )2(ϕ+∏t Tis the phase of the current. The quantity ϕ is the initial phase of the current (for t=0) and is termed the epoch angle. The phase of a current continuously increases with time. When it has increase by π2, the whole cycle of changes is repeated exactly all over again. Therefore, s peaking of the phase of a current, it is customary to drop the integer π2 and to consider the phase within π± or between zero and π2.The above change of phase by π2 occurs during the period T. therefore, the rate of change of the phase is given by T /2π. It is symbolized by the Greek letter ω(omega) and is called the pulsatance. Noting that T f /1=, we may writef T ππω2/2==The above expression, relating ω and f ,has been responsible for the fact that the pulstance ω is also termed the angular velocity or frequency. It is expressed in radians per second. Thus, for Hz f 50= , s rad /314=ω. Introduce ω in Eq.(4.1) we obtain)sin(ϕω+=t I I mSinusoidal current of the same frequency, but differing in amplitude and epoch angles, are shown in Fig.4.2. their instantaneous values are)sin(111ϕω+=t I i m )sin(222ϕω+=t I i m The time t or the product t ω,proportional to time, is laid off as abscissa.The epoch angle is always measured between the origin of coordinates, whichcorresponds to the reference time t=0, and the instant when a given sinusoidal just passes through zero(from negative to positive values). For 1ϕ>0, the start(or zero point) of the sinusoid 1i is shifted to the left, and for 2ϕ<0 it is shifted to the right of the origin of coordinates.Alternatively, the instantaneous value of a sinusoidal current may be represented by a cosinusoidal function of the formθω+=t I i m cos()Where 2/πϕθ-=.When two or more sinusoidal function differ in time phase as reckoned from similar points, they are said to be shifted or displaced in phase with respect to one another. Thisphase shift, or the phase displacement, is measured between their respective zeros, and obviously is the difference in epoch angles. Referring to Fig.4.3, 021>-ϕϕ, and the current 1i is said to lead the current 2i in phase by 21ϕϕ-, or, which is the same, the current 2i lags in phase behind the current 1i by 21ϕϕ-.Two sinusoidal functions of the same frequency are said to be in phase if they have same epoch angle, and are said to be in anti-phase when their phase displacement is π±. Finally, they are said to be in quadrature if their difference is 2/π±.中文译文：交流电交流电在电路中是一个随时间变化的值。

科技英语阅读（EST科技英语阅读（EST Reading）课后习题答案Unit 1 MathematicsPart I EST Reading1. Who is Bertrand Russell?Bertrand Arthur William Russell (b.1872 –d.1970) was a British philosopher, logician, essayist and social critic best known for his work in mathematical logic and analytic philosophy. His most influential contributions include his defense of logicism (the view that mathematics is in some important sense reducible to logic), his refining of the predicate calculus introduced by Gottlob Frege (which still forms the basis of most contemporary logic), his defense of neutral monism (the view that the world consists of just one type of substance that is neither exclusively mental nor exclusively physical), and his theories of definite descriptions and logical atomism. Russell is generally recognized as one of the founders of modern analytic philosophy, and is regularly credited with being one of the most important logicians of the twentieth century.2. What is Russell’s Paradox?Russell discovered the paradox that bears his name in 1901, while working on his Principles of Mathematics (1903). The paradox arises in connection with the set of all sets that are not members of themselves. Such a set, if it exists, will be a member of itself if and only if it is not a member of itself. The paradox is significant since, using classical logic, all sentences are entailed by a contradiction. Russell's discovery thus prompted a large amount of work in logic, set theory, and the philosophy and foundations of mathematics.Section C Post-reading TaskReading Comprehension1. Directions: Work on your own and fill in the blanks with the main idea.Part 1 (Para. 1): Brief introduction to Russell’s paradoxPart 2 (Paras. 2-5): The effect of Russell’s paradox on Gottlob Frege’s system.Para. 2: Russell’s paradox dealt a heavy blow to Frege’s attempts to develop a foundation for all of mathematics using symbolic logic.Para. 3: An illustration of Russell’s parado x in terms of sets Para. 4: Contradiction found in the set.Para. 5: Frege noticed the devastating effect of Russell’s paradox on his system and inability to solve it.Part 3 (Paras. 6-8): Solutions offered by mathematicians to Russel’s paradoxPara. 6: Russell’s own response to the paradox with his "theory of types."Para. 7: Zermelo's solution to Russell's paradoxPara. 8: What became of the effort to develop a logical foundation for all of mathematics?Part 4 (Para. 9): Correspondence between Russell and Frege on the paradoxVocabulary and Structure2. Directions: Complete the sentences with the words given in the brackets. Change the form if necessary.1) The key to unraveling such apparent paradoxes is to characterize the initial set of possibilities ("initial" meaning before you receive any extra information) and then to eliminate possibilities based on that extra information. (base)2) Indeed, this separation of meaning is reflected by the definition of "weak" in the OALD, with adistinct sense reserved for its use when pertaining to that of solutions (definition)3) The resulting radical pollution control programme outlined by Nixon, calling for a 90 per cent reduction in vehicle emissions by 1980, not only led to him being credited (albeit briefly) as policy initiator of an environmental clean-up but also provided him with the chance to deal a blow to one of his most important opponents in the 1972 elections, Edmund Muskie (blow)4) Singapore's continuing investments in education and training has brought a tenfold increase in our pool of Information Technology professionals and the Singapore worker has been consistently rated by BERI as the world's best in terms of technical skills, attitude and productivity. (term)5) In this work he was led to topology, a still new kind of mathematics related to geometry, and to the study of shapes (compact manifolds) of all dimensions. (lead)6) If there is no allowable string which spans the whole graph, then we can search in the same way as described above, but wherever the required path does not exist in the tree, check if that position in the tree is flagged for end-of-word (way)7) During the past century, steps forward in physics have often come in the form of newly found particles; in engineering, more complex devices; in astronomy, farther planets and stars; in biology, rarer genes; and in chemistry, more useful materials and medications. (form)8) A second reason for measurements is the more theoretical, put by Love as " the discovery of numerical relations between thequantities that can be measured to serve as a basis for the inductive determination of the form of the intrinsic energy function. " (serve)9) Thus the optimum conditions for coastal terrace development would seem to be areas with small tidal ranges. Finally, tidal range is an important factor in the generation of tidal currents which may locally become of geomorphological importance (become)10) The original double entrance doors to the booking hall had been replaced by an utterly incongruous picture window as had adjacent booking hall and waiting room windows. (replace)3. Directions: Reorder the disordered parts of a sentence to makea complete sentence.1) A simple way to describe topology is as a 'rubber sheet geometry' — topologists study those properties of shapes that remain the same when the shapes are stretched or compressed.2) Since the mid-1990s scientists have floated the idea that representations of numeric quantities, whether expressed as digits or as written words, are codified by the parietal cortex, a higher-processing region in the brain located just above the forehead.3) As activity was monitored, located just above the forehead ,researchers noted changes under the assumption that the brain reduces activity as it becomes accustomed to a stimulus and then reactivates when a novel stimulus is presented.4) That has not stopped physicists from devising new algorithms for the devices, which can calculate a lot faster than ordinary computers—in fact, exponentially faster, in quite a literal sense.5) Such a device would be made of metamaterial, a thicket ofmetal rings or other shapes that bends light in funny ways.4. Directions: Change the following sentences into nominalized ones.1) The passage of night could be marked by the appearance of 18 of these stars.2) The full proof of Fermat's Last Theorem is contained in these two papers.3) The concept of fixed-length hours, however, did not originate until the Hellenistic period.4) There is a probability that my first sock is red because only one of the remaining three socks is red.5) The importance of accurate data in quantitative modeling is central to using Bayes's theorem to calculate the probability of the existence of God.Discourse Understanding1. C. A "3 percent margin of error" means that there is a 95 percent chance that the survey result will be within 3 percent of the population value.2. E. How is it that a survey of only 1,000 people can reach this level of accuracy?3. G. The margin of error depends inversely on the square root of the sample size.4. A. The margin of error is a mathematical abstraction, and there are a number of reasons why actual errors in surveys are larger.5. F. Finally, the 3 percent margin of error is an understatement because opinions change. Section A Pre-reading Task1. Who discovered the Mandelbrot set?This is not a trick question, not easy to answer. Many peopleincluding Mandelbrot have laid claim to the discovery.2. Why was the set named after Benoit B. Mandelbrot?The set is named after Benoit B. Mandelbrot, a mathematician at the IBM Thomas J. Watson Research Center because he coined the term fractal to describe phenomena (such as coastlines, snowflakes, mountains and trees) whose patterns repeat themselves at smaller and smaller scales.3. Why has there been so much controversy about who discovered the Mandelbrot set? Mandelbrot claims that he and he alone discovered the Mandelbrot set, but there are other mathematicians who have challenged his claim.4. What did the challengers say abo ut Mandelbrot’s claim of discovery?Two mathematicians said that they independently discovered and described the set at about the same time as Mandelbrot did. And another mathematician also asserted that his work on the set not only predated Mandelbrot's efforts but also helped to guide them5. Why did some professors support Mandelbrot’s claim?Mandelbrot deserves to have the set named after him, because his efforts brought the set to the attention of both the public and of the pure-mathematics community.Section C Post-reading TaskLanguage in Use1. Match the Chinese in the left column with the English in the right column.迭代函数iterative function优先权之争priority battle分形特征fractal properties有意义make sense以越来越小的规模重复同一模式patterns repeat themselves at smaller and smaller scales混沌理论chaos theory季刊a quarterly journal数学界the mathematics community波纹线crisp lines会议公报proceedings of a conference2. Join the following short sentences into longer ones.e.g. a. A fractal is generally a rough or fragmented geometric shape .b. The shape can be subdivided in parts.c. each part is (at least approximately) a reduced-size copy of the whole, a property calledd. each part has a property of self-similarity.e.g. A fractal is generally "a rough or fragmented geometric shape that can be subdivided in parts, each of which is (at least approximately) a reduced-size copy of the whole", a property called self-similarity.1) In addition to coining the term "fractal" to describe objects and surfaces which are irregular at various dimensions of scale, he also introduced such concepts as "fractal dimensions" and the particular fractal known as the Mandelbrot set, frequently represented with the mathematical formula z → z2 + c.2) It appeared that things were settling into a pleasant and fruitful routine, with his school lessons supplemented by long talks with his uncle about classical analysis, the iterative work of Pierre Fatou and the equally fascinating Julia Sets generated by Gaston Julia3) Just as the youthful Mandelbrot had passed his college entrance exams by translating algebraic problems intogeometrical problems, and solving them by intuitively deducing the "perfected" shape, he here realized there was something deeper, something mathematical, behind these strange patterns.4) But the beauty in Mandelbrot's models was not that they generated a deceitful randomness, but that they could generate graphed data whose visual pattern accurately mimicked the visual patterns created by real phenomena。

伯特兰·罗素《弗兰西斯·培根》（中英文互译）伯特兰·阿瑟·威廉·罗素（Bertrand Arthur William Russell，1872—1970），英国哲学家、数学家、逻辑学家、历史学家、文学家，分析哲学的主要创始人，世界和平运动的倡导者和组织者，主要作品有《西方哲学史》《哲学问题》《心的分析》《物的分析》等。

罗素不仅在哲学、逻辑和数学上成就显著，在教育学、社会学、政治学和文学等许多领域也都颇有建树。

Francis Bacon弗兰西斯·培根FRANCIS BACON (1561-1626), although his philosophy is in many ways unsatisfactory, has permanent importance as the founder of modern inductive method and the pioneer in the attempt at logical systematization of scientic procedure. ...弗兰西斯·培根（1561—1626）是近代归纳法的创始人，又是给科学研究程序进行逻辑组织化的先驱，所以尽管他的哲学有许多地方欠圆满，他仍旧占有永久不倒的重要地位。

……Bacon's most important book, The Advancement of Learning, is in many ways remarkably modern. He is commonly regarded as the originator ofthe saying "Knowledge is power," and though he may have had predecessors who said the same thing, he said it with new emphasis. The whole basis of his philosophy was practical: to give mankind mastery over the forces of nature by means of scientific discoveries and inventions. He held that philosophy should be kept separate from theology, not intimately blended with it as in scholasticism. He accepted orthodox religion; he was not the man to quarrel with the government on such a matter. But while he thought that reason could show the existence of God, he regarded everything else in theology as known only by revelation. Indeed he held that the triumph of faith is greatest when to the unaided reason a dogma appears most absurd. Philosophy, however, should depend only upon reason. He was thus an advocate of the doctrine of "double truth," that of reason and that of revelation. This doctrine had been preached by certain Averroists in the thirteenth century, but had been condemned by the Church. The "triumph of faith" was, for the orthodox, a dangerous device. Bayle, in the late seventeenth century, made ironical use of it, setting forth at great length all that reason could say against some orthodox belief, and then concluding "so much the greater is the triumph of faith in nevertheless believing." How far Bacon's orthodoxy was sincere it is impossible to know.培根的最重要的著作《崇学论》在许多点上带显著的近代色彩。