Hansen and Nielsen (Inventory of Archaic and Classical Poleis [Oxford 2004]) set out to answer this question for the Archaic and Classical periods. They collected all source mentions of ancient Greek settlements (primarily epigraphic, supplemented by literary) and, along with early historical and archaeological data from the emerging Barrington Atlas, categorized all known sites. Through this process they and their collaborators struggled with definitions, and this is all outlined in the extensive introduction. In simple terms, they ultimately used a small but wide-ranging set of basic criteria to deem a place a Greek polis or not, and most of those criteria pertain to a location's ability to determine its own affairs in at least a few key areas. Within their ultimate definition there is a gigantic range and variety, from emerging macro-states like the Athenian hegemonic politeia or the Spartan "coalition" to very small urban centers which are barely mentioned in sources at all and only exist in the archaeological record. Many of the smallest don't even have names.

Their first category is organizational: is there any cohesion in the place in question? is the nature of that cohesion political (all its inhabitants act together towards common political ends, like support of a single ruler, participating in a council which has authority over them all, voting etc); is the nature of the cohesion territorial (the inhabitants are all grouped by some method into a lump, by geography or artificial borders); or is the nature of the cohesion urbanization. All three of these categories bleed into one another but mix and match--for instance, a place might have no urban center at all, just a relatively even distribution of small holdings which all still participate in a common political understanding and are geographically bounded by mountains or swamps. One category I think could also be useful in this is religious: do the people of a given place all participate in rites at the same temple(s), and do the locations of those temples serve to delineate borders (like the Heraion out in the Argolid plain, as De Polignac argued).

Along side this definition of cohesion, the work identifies activities which are characteristic of a polis in the Greek world. Most of them have to do with self-governance in some way or another:

• the community strikes its own coins

• the community sends athletes to Pan-Hellenic games

• the community has a prytaneion (a sort of central sacred hearth of a town) or a bouleterion (a council-hall where collective political action occurs)

• the community engages in warfare on its own terms, with fighters which are drawn from itself and fight for it, against opponents clearly defined as other/neighbor/bordering

• the community is a participant in a larger federation of such communities

• the community issues decrees of proxeny (an honorific status of inclusion granted to an individual considered an outsider to the community)

Based on the above, the collaborators assigned each place they found to a set of types. Type [A] places are called a polis by at least one ancient source, regardless of the type(s) of cohesion; type [B] are places which are never called a polis in any source, but we are pretty sure they qualified in cohesion and participation in at least one of the above; and type [C], which are vaguely still candidates for official polis status for one reason or another, but are very hard to pin down with available evidence.

The city states (poleis) of Ancient Greece were fiercely independent in spirit and constantly fighting each other. Most also ruled a rural hinterland where the smaller communities were under the sway of the polis, such as Attica (Athens) and Laconia (Sparta).

There were wider regional states that were normally governed by a particular polis, like Boeotia (Thebes) but in these the larger subject communities might frequently seek more independence. Hence in Boeotia, Orchomenos was often at odds with Thebes, while Plataea, which was geographically within the region, always affiliated itself with Athens to the extent that eventually Thebes destroyed it.

Then there were much larger regions, mostly to the north, that were less developed politically and socially and were nominally ruled by kings, like Macedonia and Thessaly, but here too they were constantly fragmenting. It was only when exceptionally able kings like Philip II of Macedonia came along that these regions seriously rivalled the poleis.

There is no simple answer to the question. Some effectively independent settlements might have populations as low as 1,000. The Greeks themselves tended to see the ideal number more in terms of the maximum; I think it was Aristotle who opined that all citizens (i.e. native-born adult males) of a polis should know each other, otherwise it was too big. Athens at the height of its power was definitely thought of as way too big.